Class Lehman_AnalyzeCongruences2
java.lang.Object
de.tilman_neumann.jml.factor.lehman.Lehman_AnalyzeCongruences2
public class Lehman_AnalyzeCongruences2
extends java.lang.Object
Analyze a-values that help the Lehman algorithm to find factors, modulo powers of 2.
If we analyze the data in terms of (a0, adjust) pairs, we notice that we always get antidiagonals, each of
them representing a "successful a", because a == (a0 + adjust) (mod m), with m=2^n. So all we need to investigate is "a" (mod m).
Version 2 doubles m step-by-step and analyzes or allows to analyze incremental changes.
Only odd k are analyzed, because the result for even k is trivial (we need all odd "a"-values).
The number of successful a from original k+N congruences are 1, 2, 6, 16, 64, 256, 1024, ...
The last incremental improvement occurs at m=16. This is trivial.
For the more interesting k*N congruences I found experimentally:
The number of successful a are a(n) = 1, 2, 6, 16, 56, 192, 736, 2816, 11136, 44032, ... (not found in OEIS)
dropped a are d(n) = 0, 2, 2, 8, 8, 32, 32, 128, 128, 512, ... (quite trivial)
From that data I derived the iterative formula
a(1) = 1
if (m > 1) {
n = ld(m);
rightExp = 2*floor(n/2) - 1
a(n) = a(n-1)*4 - 2^rightExp
}
having first values
n= 1, m= 2: a(n) = 2^0 = 1
n= 2, m= 4: a(n) = (2^0)*4 - 2^1 = 2^2 - 2^1 = 2
n= 3, m= 8: a(n) = (2^2 - 2^1)*4 - 2^1 = 2^4 - 2^3 - 2^1 = 6
n= 4, m= 16: a(n) = (2^4 - 2^3 - 2^1)*4 - 2^3 = 2^6 - 2^5 - 2^4 = 16
n= 5, m= 32: a(n) = (2^6 - 2^5 - 2^4)*4 - 2^3 = 2^8 - 2^7 - 2^6 - 2^3 = 56
n= 6, m= 64: a(n) = (2^8 - 2^7 - 2^6 - 2^3)*4 - 2^5 = 2^10 - 2^9 - 2^8 - 2^6 = 192
n= 7, m= 128: a(n) = (2^10 - 2^9 - 2^8 - 2^6)*4 - 2^5 = 2^12 - 2^11 - 2^10 - 2^8 - 2^5 = 736
n= 8, m= 256: a(n) = (2^12 - 2^11 - 2^10 - 2^8 - 2^5)*4 - 2^7 = 2^14 - 2^13 - 2^12 - 2^10 - 2^8 = 2816
n= 9, m= 512: a(n) = (2^14 - 2^13 - 2^12 - 2^10 - 2^8)*4 - 2^7 = 2^16 - 2^15 - 2^14 - 2^12 - 2^10 - 2^7 = 11136
n=10, m=1024: a(n) = (2^16 - 2^15 - 2^14 - 2^12 - 2^10 - 2^7)*4 - 2^9 = 2^18 - 2^17 - 2^16 - 2^14 - 2^12 - 2^10 = 44032
...
Computing more values from the iterative formula gives the sequence (starting at n=1)
a(n) = 1, 2, 6, 16, 56, 192, 736, 2816, 11136, 44032, 175616, 700416, 2799616, 11190272, 44752896, 178978816, 715882496, 2863398912, 11453464576, 45813334016, 183252811776, 733009149952, 2932034502656, 11728129622016, 46912510099456, 187650006843392, 750599993819136, 3002399841058816, 12009599230017536, 48038396383199232, ...
Closed formulas I found later on:
a(n) = 2^(n-2) * A023105(n), for n>0
a(2n+2) = 2*A083086(2n), for n>=0
-
Constructor Summary
Constructors Constructor Description Lehman_AnalyzeCongruences2()
-
Method Summary
Modifier and Type Method Description long
findSingleFactor(long N, int m)
static void
main(java.lang.String[] args)
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
-
Constructor Details
-
Lehman_AnalyzeCongruences2
public Lehman_AnalyzeCongruences2()
-
-
Method Details
-
findSingleFactor
public long findSingleFactor(long N, int m) -
main
public static void main(java.lang.String[] args)
-