+/EE360P

distributed systems

git clone https://git.julia.blue/+/EE360P

vijaygarg1init07ca65d

master
2.4 KiB78 linesraw
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 {
31  protected final Product product = new Product();
32
33  protected long N;
34  protected long N_I;  // N'
35  protected long R;
36  protected long R_1;  // R - 1
37  protected int s;
38
39  /** Set the modular and initialize this object. */
40  Montgomery set(long n) {
41    if (n % 2 != 1)
42      throw new IllegalArgumentException("n % 2 != 1, n=" + n);
43    N = n;
44    R = Long.highestOneBit(n) << 1;
45    N_I = R - Modular.modInverse(N, R);
46    R_1 = R - 1;
47    s = Long.numberOfTrailingZeros(R);
48    return this;
49  }
50
51  /** Compute 2^y mod N for N odd. */
52  long mod(final long y) {
53    long p = R - N; 
54    long x = p << 1;
55    if (x >= N) x -= N;
56    
57    for(long mask = Long.highestOneBit(y); mask > 0; mask >>>= 1) {
58      p = product.m(p, p);
59      if ((mask & y) != 0) p = product.m(p, x);
60    }
61    return product.m(p, 1);
62  }
63
64  class Product {
65    private final LongLong x = new LongLong();
66    private final LongLong xN_I = new LongLong();
67    private final LongLong aN = new LongLong();
68
69    long m(final long c, final long d) {
70      LongLong.multiplication(x, c, d);
71      // a = (x * N')&(R - 1) = ((x & R_1) * N') & R_1
72      final long a = LongLong.multiplication(xN_I, x.and(R_1), N_I).and(R_1);
73      LongLong.multiplication(aN, a, N);
74      final long z = aN.plusEqual(x).shiftRight(s);
75      return z < N? z: z - N;      
76    }
77  }
78}