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)