Wskazówka do zmniejszania liczności sprawdzanych przypadków podczas faktoryzacji

Dotychczas moje algorytmy przekształcały rozkładaną liczbę. Aby podliniowo faktoryzować, należy skorzystać z właściwości dzielników. Można je uzyskiwać nawet nie znając tych dzielników. Zainteresowych odsyłam, by zapisać kolejne cyfry liczby w innych systemach, oraz sposób odwrócenia kolejności dwu ostatnich podstaw, co już daje nieco informacji o dzielnikach...

Pomocą może być także funkcja wskazująca rozmieszczenie liczb pierwszych, bliźniaczych, czworaczych, opublikowana już na tym blogu. Rozszerzenie nie musi być o kolejną liczbę pierwszą, lecz o dowolną liczbę pierwszą. 

Liczba jest pierwsza, gdy wspomniana funkcja przyjmuje wartość 1 dla każdego rozszerzenia mniejszego niż dana liczba. Pojawiającą się drobną nieoznaczoność przy nie kolejnych liczbach pierwszych można łatwo namierzyć, np. dla k=6 i rozszerzaniu o liczbę p będzie sugerowana własność pierwszości dodatkowo tylko dla p oraz 5*p, gdy nie uwzględniamy liczby pierwszej 5. Dla p pierwszej wartość funkcji tych miejsc ulega modyfikacji z 1 do p. Funkcja z liczby ma wartość a>1, gdy liczba ta jest podzielna przez a.

A kiedy weźmiemy za mało danych, do gry wchodzi chińskie twierdzenie o resztach, dzięki któremu obszar poszukiwań dzielników drastycznie się kurczy. 

Wystarczy funkcja dla p \in {2, 3, 5, 7}, a znajdziemy rozkład 7387, mając reszty modulo: 6, 30=6*5, 42=6*7. Te same dane (już bez chińskiego twierdzenia o resztach) wystarczyły na wykazanie pierwszości 127. I tylko warto przyjmować rozkład liczb ujemnych, np. testując -5 = (-1)*5 lub -5 = 1*(-5), i jeszcze parę innych związanych zależnościami, by dopasować iloczyny reszt dzielników. Unikamy w ten sposób testowania wielu wartości. 

Nie chcę podawać tu szczegółów - to jest za szybkie na obecne zabezpieczenia cyberbezpieczeństwa. Przy rozkładzie 7387 użyte tylko cztery liczby pierwsze spośród 23 kandydatów już wskazały rozkład... Wystarczyło uzgodnić 30*a+r1 = 42*b+r2, gdzie a, b małe liczby; r1, r2 pozycje funkcji z wartością 1 dla parametrów {2,3, 5 | 7}. w której r1,r2 przystają do wyznaczonej reszty, np. -5 = 37-42, zaś 37 jest resztą iloczynu a*b (mod 42). Reszta będąca liczbą pierwszą to nie jest przypadek...

 

Kod faktoryzacji przeglądem zupełnym, zakres podstaw większy niż sqrt n

Kod w poprzednim poście można przedłużyć, i teraz zaprezentuję to przedłużenie. To też jest algorytm faktoryzacji, tutaj "odwracający" kierunek sprawdzeń w tym sensie, że współczynnik a maleje od pierwiastka kwadratowego z liczby rozkładanej n do 1. 

Kod ma 'tylko' pierwiastek kwadratowy z n iteracji. Jednak w testach okazał się wolny. Zaprezentuję go z funkcją użytą w poprzednim kodzie, conversion1(n,p), która wyraża liczbę w postaci c*p*p+a*p+b = n dla c=0. Chociaż dla tych wartości lepiej użyć modyfikacji pobranych z rozwinięcia (a-1)*(b+1) = a*b+b-a-1. Dzielenie będzie zastąpione dodawaniem i odejmowaniem.
Jeszcze jedna uwaga, użyta funkcja floorSqrt(n) zwraca całkowito-liczbowy pierwiastek kwadratowy oraz jego różnicę od wartości, tzn. jeśli f,g = floorSqrt(n), to n = f*f+g, 0 <= g < 2*f+1. 

Numery linii oznaczają wcięcia, jak przy bardziej dopracowanych, publikowanych przeze mnie kodach w Pythonie 2.

0def factor4(n):
1  a,b = floorSqrt(n)
1  if 0==b and n==a*a: return [a,a]
1  p = a
1  k=1
1  while 1<a:
2    if b<a:
    #  if 1==p%2: #dzielnik bywa pomijany np. 55
    #    p+=2
    #    k=2
    #  else:
3      p+=1
3      k=1
3      c,a,b = conversion1(n,p)
2    else:
3      k = b/a
3      if 0==b%a:
4        p += k
4        q = n/p
4        print "dzielnik p",p, q
4        return [p,q]       
3      p = p+k+1
3      c,a,b = conversion1(n,p)
2    print "[",a,",",b,"]_",p,"   ",k  
1  return [n]
 

Zakomentowana instrukcja if miała zmiejszyć krotność iteracji dla wartości nieco większych niż sqrt n, by sprawdzać tylko nieparzyste, ale okazało się, że niektóre iloczyny nie są wtedy rozkładane. Taką liczbą jest 55 = 5*11.

Kod ma kolejną wadę opóźniajacą faktoryzację: zwraca wartość będącą pierwszą [n], lub dwie [p,q], ale nie wiadomo, czy p oraz q są pierwsze czy złożone. Zatem funkcja wywołująca factor4(n) musi ją wywołać ponownie dla tych wartości. Przy programowaniu współbieżnym wyniki można odkładać do tablic, i rzut wskaźnikiem (czytaj: rzut okiem) na długości tych tablic wskazuje, czy dzielniki są znalezione, jakie są, ale to nie będzie pełny rozkład. 

Tak też można...

Kod faktoryzacji szukaniem przeniesień podczas konwersji

Udało mi się zbudować kolejny kod faktoryzacji, w którym lokalizuję i sprawdzam przeniesienia występujące podczas konwersji na coraz większe podstawy. Dla małych wartości ma narzut obliczeniowy, który jednak jest kompensowany dla liczb kilkunastocyfrowych. Liczba, którą innym przeglądem zupełnym rozkładałem (i zatrzymywałem po kilkunastu godzinach gdy podstawa systemów przekroczyła milion), tą wersją uległa rozłożeniu na czynniki w 2h 13 minut. 

Program nie ma już pętli wykonującej się (sqrt N) /2 razy, przeskakuje część iteracji, gdy wiadomo, że nie ma przeniesienia podczas konwersji, a zatem nie ma kandydata na dzielnik. Ile razy wykona się pętla? Nie wiem. Są obszary, kiedy w sekundy obrabia setki tysięcy podstaw w sekundę (liczba 16-cyfrowa), a są inne, w którym przeniesienia podczas konwersji są co kolejną podstawę. 

Kiedy zażyczyłem sobie, żeby program starał się jednak zwiększać podstawę o co najmniej 2, mógł przeskoczyć dzielnik, ale kiedy dołączyłem warunek parzystości podstawy, ta sama liczba co wspomniana już została rozłożona na czynniki w godzinę 8 minut... Prawie 50 procent szybciej.

Podaję kod 'jak powstał', w którym conversion1(n,p) polega na przedstawieniu liczby w systemie o podstawie p, zaś dalej(...,p,k) to konwersja na system p+k bez wykonania przeniesień ([a,b,c] => [a, b-2k*a, c-k*b+k*k*a]), by je lokalizować w tym przedziale. Na podstawie tych postaci przekształconej liczby dobieramy skok k. Można go jeszcze usprawnić... 

def factorize(n):
  divisors = []
  while 0==n%2:
    divisors.append(2)
    n/=2
  p=p1=3
  a1,b1,c1 = conversion1(n,3)
  k=2
  a=0 #,b1,c1,p1 = conversion(a,b,c,p,k)
  while a1!=a:
    a,b,c,p = a1,b1,c1,p1
    if 0==c:
      if 0==n%p1:
        divisors.append(p1)
        n/=p1
        a1,b1,c1 = conversion1(n,p1)
        continue
      c = n%p1
      b = ((n-c)/p)%p
      a = (n-b*p*a)/(p*p)
    p1 = p+k
    a1,b1,c1 = conversion1(n,p1)
    #print "[",a,",",b,",",c,"]_",p,"   ",
    print "[",a1,",",b1,",",c1,"]_",p1         
 
  print "dalej teraz a maleje do 1"
  print "[",a1,",",b1,",",c1,"]_",p1,"  druga czesc"
  if b1<a1:
    a1-=1
    b1+=p1
  while 0<a1: #szukanie binarne k
    k3 = b1/a1/2
    k1,k2 = 0,k3     
    a3,b3,c3,p3 = a1,b1,c1,p1
    a,b,c,p = a1,b1,c1,p1
    while k1<k2-1:
      k = k1+(k2-k1)/2
      a,b,c,p = dalej(a1,b1,c1,p1,k)
      p3 = p1+k
      a3,b3,c3 = conversion1(n,p3)
      #print "[",a,",",b,",",c,"]_",p,"   ",k1,k,k2,"  ",
      #print "[",a3,",",b3,",",c3,"]_",p3,"   "
      if b3>a3 and 0<c:
        k1=k
      else:
        k2=k
    print "[",a1,",",b1,",",c1,"]_",p1,"   ",
    print "[",a,",",b,",",c,"]_",p,"   ",k1,k,k2,"  ",
    print "[",a3,",",b3,",",c3,"]_",p3,"   "
    if b3<a3:
      a1,b1,c1,p1 = a3-1,b3+p3,c3,p3
    else:
      if 2>k and 1==p1%2:
        k=2
      p1 = p1+k
      a1,b1,c1 = conversion1(n,p1)
    print "po [",a1,",",b1,",",c1,"]_",p1
    if 0==c1:
      while 0==n%p1:
        divisors.append(p1)
        n/=p1
      a1,b1,c1 = conversion1(n,p1)
     
  if 1<n:
    divisors.append(n)
  return divisors