25 kwietnia 2018

Własność liczb złożonych

Liczby złożone można zapisać w postaci tożsamości:
2N = 2p*q
= (a-b)(a+b+1) = (a-b)*(a+b) + (a-b) = a^2 - b^2 + a - b
= a(a+1)-b(b+1)
Dla liczby nieparzystej N o dzielnikach nieparzystych czynniki (a-b), (a+b+1) mają różną parzystość.
Porównując ten wzór z szeregiem harmonicznym uzyskujemy, że 2N można przedstawić jako różnicę dwu sum skończonych szeregów harmonicznych, na które ogólny wzór jest
1+2+...+n = n(n+1)/2 .
Np. 2*8934053 = 8762*8763 - 7675*7676 =
sum _{0<i<8763} i - sum _{0<i<7676} i.
Ekstremalne przypadki są przy jak najmniejszych wartościach a~sqrt N, oraz b bliskim sqrt (a(a+1)-N).
Drugi ekstremalny przypadek jest przy a=N, b=N-1:
N(N+1) - (N-1)N = 2N

Oznaczmy funkcję r(N, a, b) daną wzorem:
r() = ( a(a+1) - 2N - b(b+1) )/2
Okazuje się, że funkcję r można ustawić w ciąg dla różnych możliwości (a,b) tak, by r była przedziałami monotoniczna, ograniczona przez 0 oraz b.
Ze względu na tożsamość
x(x+1) = 2x + (x-1)x
zmiana a, b o 1 powoduje zmianę r() o a, b odpowiednio.
Funkcja r() zeruje się, gdy a-b jest dzielnikiem N. Także kiedy r() dzieli b, rozkład a-b zawiera dzielnik N.

Na razie jest tu wiele niewiadomych. Na pewno tej postaci nie można jeszcze zastosować do algorytmu faktoryzacji, ale znajdowanie lokalnych minimów r() jest stosunkowo łatwe do przeprowadzenia, np. równaniem kwadratowym, metodą połowienia.
Sam algorytm wstępnie może wyglądać następująco:
a = sqrt (2N), b = sqrt( a(a+1)-2N ), r= ( a(a+1)-2N-b(b+1) )/2 
while( a-b>1 ) {
  a++; r+=a; 
  while( r>b-1 ) {
    b++; r-=b;
  }
  if( 0==r ) return dzielnik a-b liczby N;
}
Potem w każdym kroku a i b się zwiększają prawie równolegle, b dogania a dla a=N.  Gdy a-b malejąc osiągnie b, warto zmienić sposób działania - pętla wewnętrzna będzie się wykonywać rzadziej niż zewnętrzna.
Nieznana jest wartość stopu, gdyż podana pętla sprawdza te same wartości na różne sposoby.  Mam podejrzenie, że wystarczy połowa sqrt(2N) przypadków przy podejściu siłowym. A kod jest niesamowicie prosty...