+/EE360P
distributed systems
git clone https://git.julia.blue/+/EE360P
07ca65d
master
1/** 2* Licensed to the Apache Software Foundation (ASF) under one 3* or more contributor license agreements. See the NOTICE file 4* distributed with this work for additional information 5* regarding copyright ownership. The ASF licenses this file 6* to you under the Apache License, Version 2.0 (the 7* "License"); you may not use this file except in compliance 8* with the License. You may obtain a copy of the License at 9* 10* http://www.apache.org/licenses/LICENSE-2.0 11* 12* Unless required by applicable law or agreed to in writing, software 13* distributed under the License is distributed on an "AS IS" BASIS, 14* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 15* See the License for the specific language governing permissions and 16* limitations under the License. 17*/ 18package org .apache .hadoop .examples .pi .math ; 19 20/** Montgomery method. 21* 22* References: 23* 24* [1] Richard Crandall and Carl Pomerance. Prime Numbers: A Computational 25* Perspective. Springer-Verlag, 2001. 26* 27* [2] Peter Montgomery. Modular multiplication without trial division. 28* Math. Comp., 44:519-521, 1985. 29*/ 30class Montgomery { 31protected final Product product =new Product (); 32 33protected long N ; 34protected long N_I ;// N' 35protected long R ; 36protected long R_1 ;// R - 1 37protected int s ; 38 39/** Set the modular and initialize this object. */ 40Montgomery set (long n ) { 41if (n %2 !=1 ) 42throw new IllegalArgumentException ("n % 2 != 1, n=" +n ); 43N =n ; 44R =Long .highestOneBit (n ) <<1 ; 45N_I =R -Modular .modInverse (N ,R ); 46R_1 =R -1 ; 47s =Long .numberOfTrailingZeros (R ); 48return this ; 49 } 50 51/** Compute 2^y mod N for N odd. */ 52long mod (final long y ) { 53long p =R -N ; 54long x =p <<1 ; 55if (x >=N )x -=N ; 56 57for (long mask =Long .highestOneBit (y );mask >0 ;mask >>>=1 ) { 58p =product .m (p ,p ); 59if ((mask &y ) !=0 )p =product .m (p ,x ); 60 } 61return product .m (p ,1 ); 62 } 63 64class Product { 65private final LongLong x =new LongLong (); 66private final LongLong xN_I =new LongLong (); 67private final LongLong aN =new LongLong (); 68 69long m (final long c ,final long d ) { 70LongLong .multiplication (x ,c ,d ); 71// a = (x * N')&(R - 1) = ((x & R_1) * N') & R_1 72final long a =LongLong .multiplication (xN_I ,x .and (R_1 ),N_I ).and (R_1 ); 73LongLong .multiplication (aN ,a ,N ); 74final long z =aN .plusEqual (x ).shiftRight (s ); 75return z <N ?z :z -N ; 76 } 77 } 78}