PollardRhoBrentMontgomeryR64Mul63 (org.matheclipse:matheclipse-gpl 3.0.0 API)

java.lang.Object
- de.tilman_neumann.jml.factor.FactorAlgorithm
- - de.tilman_neumann.jml.factor.pollardRho.PollardRhoBrentMontgomeryR64Mul63

```
public class PollardRhoBrentMontgomeryR64Mul63
extends FactorAlgorithm
```
Brents's improvement of Pollard's Rho algorithm using Montgomery multiplication. This version combines the Montgomery reducer R=2^64 with mul63(). It is significantly faster than PollardRhoBrentMontgomery64 for N < 58 bits, because until that size the performance advantage of mul63() vs. mul64() predominates the performance loss caused by errors in Montgomery multiplication. Another small performance gain stems from the choice of polynomials: x_(n+1) = x_n*(x_n + 1) is slightly faster than x_(n+1) = (x_n)^2 - c because it does not need another reduction (mod N) after subtracting c.

Author:

Tilman Neumann

Field Summary
- Fields inherited from class de.tilman_neumann.jml.factor.FactorAlgorithm
  DEFAULT, NUM_PRIMES_FOR_31_BIT_TDIV, tdivLimit

Constructor Summary

Constructors
Constructor Description

PollardRhoBrentMontgomeryR64Mul63()

Method Summary

All Methods Static Methods Instance Methods Concrete Methods
Modifier and Type	Method	Description
`long`	`findSingleFactor(long N)`
`BigInteger`	`findSingleFactor(BigInteger N)`	Find a single factor of the given N, which is composite and odd.
`String`	`getName()`
`static void`	`main(String[] args)`	Test.
`static long`	`montMul63(long a, long b, long N, long Nhat)`	Montgomery multiplication of a*b mod n with regard to R=2^63.

Methods inherited from class de.tilman_neumann.jml.factor.FactorAlgorithm
factor, factor, searchFactors

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Constructor Detail
  - PollardRhoBrentMontgomeryR64Mul63
```
public PollardRhoBrentMontgomeryR64Mul63()
```
- Method Detail
  - getName
```
public String getName()
```
    Specified by:
    
    getName in class FactorAlgorithm
    
    Returns:
    
    The name of the algorithm, possibly including important parameters.
  - findSingleFactor
```
public BigInteger findSingleFactor(BigInteger N)
```
    Description copied from class: FactorAlgorithm
    
    Find a single factor of the given N, which is composite and odd.
    
    Specified by:
    
    findSingleFactor in class FactorAlgorithm
    
    Returns:
    
    factor
  - findSingleFactor
```
public long findSingleFactor(long N)
```
  - montMul63
```
public static long montMul63(long a,
                             long b,
                             long N,
                             long Nhat)
```
    Montgomery multiplication of a*b mod n with regard to R=2^63. ("mulredc63x" in Yafu)
    
    Parameters:
    
    a -
    
    b -
    
    N -
    
    Nhat - complement of N mod 2^63
    
    Returns:
    
    Montgomery multiplication of a*b mod n
  - main
```
public static void main(String[] args)
```
    Test. Test numbers: 3225275494496681 (52 bits) = 56791489 * 56791529 322527333642009919 (59 bits) = 567914891 * 567914909 3225273260887418687 (62 bits) = 567914891 * 5679148957
    
    Parameters:
    
    args - ignored