[Algorytmy] Program do faktoryzacji liczb

[Elayne]

Pare miesięcy temu zainteresowałem się faktoryzacją liczb i w związku z tym miałbym pytanie.
Czy jest jakiś program komputerowy (najlepiej na licencji open source) który umożliwiłby automatyczną siłową faktoryzację dużych liczb (brute-force) według własnego algorytmu który wyglądałby mniej więcej tak:
1. - sprawdzenie czy faktoryzowana liczba nie jest liczbą pierwszą
2. - podstawienie liczby z danego zbioru do wzoru;
3.-- sprawdzenie warunków na wyniku równania:
--- jeśli warunek nie jest spełniony przejście do punktu 2 i podstawienie kolejnej liczby,
--- jeśli warunek jest spełniony podstawienie wyniku do drugiego równania;
4. - sprawdzenie warunków na wyniku drugiego równania:
--- jeśli warunek nie jest spełniony przejście do punktu 2 i podstawienie kolejnej liczby,
--- jeśli warunek jest spełniony podstawienie wyników do trzeciego równania i wyświetlenie poszukiwanych liczb.

Od programu bym wymagał aby poprawnie wykonywał podstawowe działania arytmetyczne na wielkich liczbach (dodawanie, odejmowanie, mnożenie, dzielenie i pierwiatkowanie) oraz sprawdzanie warunków.
Ilość kombinacji do sprawdzenia w tym algorytmnie nie jest ściśle uzależniony od wielkości liczb. Przykłady: aby rozłożyć 4.295.229.443 na 65.537 i 65.539 (jeśli je pomnożymy uzyskamy 4.295.229.443) trzeba sprawdzić tylko 1 kombinację. By rozłożyć 679 należy sprawdzić max. 6 kombinacji, natomiast aby rozłożyć klucz RSA-704 (212 cyfr) w najgorszym przypadku należałoby sprawdzić \(\displaystyle{ 4 \cdot 10^{52}}\) kombinacji.
Udało mi się sprawdzić w arkuszu kalkulacyjnym że algorytm ten poprawnie znajduje iloczyn dwóch liczb pierwszych dla liczb do 18 cyfr.

Innym rozwiązaniem tego zagadnienia jest znalezienie jakiegoś prostego rozwiązania na szybkie obliczenie równania z dwiema niewiadomymi-zmiennymi. Spróbuję to zilustrować: mamy drogę na której rostawiono przystanki według ciągu np.: \(\displaystyle{ \frac{n(n+1){}{2}}\) t.j 0,1,3,6,10,15,21 ... itd (+1,+2,+3,+4,+5 ... +n). Z miejsca n=0 rusza samochód z prędkością a=9 na jednostkę czasu i przyśpiesza o a+2 po upływie każdego okresu czasu t.j 9,11,13,15,17,19 ... itd. Po pierwszym okresie samochód będzie pomiędzy przystankami 6 i 10, po zakończeniu drugiego okresu będzie pomiędzy przystankami 15 i 21. Rozwiązaniem tego zagadnienia jest podanie po którym okresie samochód będzie po raz pierwszy na przystanku a nie pomiędzy przystankami. Licząc wszystko po kolei mozna uzyskać rozwiązanie dla tego przykładu którym jest 6 okres i 14 przystanek (105). Ale takie podejście nie sprawdzi się przy dużych liczbach - za dużo kombinacji do sprawdzenia.

[Xitami]

do zabaw z liczbami polecam kapitalny, darmowy, lekki, programowalny superkalkulator

Kod: Zaznacz cały

http://pari.math.u-bordeaux.fr/

AU

pari-gp-tlarge.png (1.32 KiB) Przejrzano 321 razy

[/url]

[Elayne]

A coś bardziej konkretnego?

Pokaże jak mniej więcej wygląda faktoryzacja którą chciałbym zrobić na kluczach RSA, to może łatwiej będzie pokazać co chciałbym zautomatyzować.
Przedstawię faktoryzację "z reszty" wspomnianej wcześniej liczby 679:
Krok pierwszy:
Szukamy pierwiastek kwadratowy który jest najbliżej liczby 679:
\(\displaystyle{ 27^2=729}\), reszta: \(\displaystyle{ 729-679=50}\)
Krok drugi:
Tworzymy zbiór par liczb: \(\displaystyle{ a=n(n+1)\ i\ 0>a<50}\) oraz n - liczba całkowita dodatnia, b=50-a

Kod: Zaznacz cały

1. - a=6*7=42 b=8
2. - a=5*6=30 b=20
3. - a=4*5=20 b=30
4. - a=3*4=12 b=38
5. - a=2*3=6  b=44
6. - a=1*2=2 b=48

Krok trzeci:
Testujemy utworzone pary:
Ad.1
\(\displaystyle{ 8 \cdot 8-50=14\ i\ (27-8)\cdot 2=38}\) - druga liczba jest większa od pierwszej, nie spełnia tym warunku
Ad.2
\(\displaystyle{ 20 \cdot 20-50=350\ i\ (27-20)\cdot 2=14}\) - warunki są spełnione
\(\displaystyle{ \frac{350}{14}=25}\) - dzieli się bez reszty, więc poszukiwaną liczbą jest \(\displaystyle{ 7 (27-20=7)}\).
Sprawdzamy wynik: \(\displaystyle{ \frac{679}{7}=97}\)
Ad.3-6
\(\displaystyle{ 30 \cdot 30-50=850}\) - nie spełnia warunku, liczba jest większa od faktoryzowanej liczby. Podobną sytuacje mamy z pozostałymi kombinacjami.
Tak więc jest tylko jedno rozwiązanie: 7 i 97.
Przepraszam jeśli to chaotycznie przedstawiłem, nie jestem matematykiem.

Ten algorytm faktoryzacji jest oparty w znacznej części na własności liczb. Paradoksalnie jeśli pomnożymy faktoryzowaną liczbę przez 2 to mamy o połowę mniejszą liczbę kombinacji do sprawdzenia - nie rozumiem do końca jak się to dzieje gdyż jest to zgoła nielogiczne. Jeśli mamy mnożenie: \(\displaystyle{ a \cdot b=c}\) i \(\displaystyle{ a<b}\) to przy faktoryzacji liczby c możemy utworzyć podobny zbiór par liczb dla poszukiwanego czynnika a. Znajdując cześć wspólną tego zbioru ze zbiorem "z reszty" możemy dokonać kolejnego zmniejszenia ilości kombinacji do sprawdzenia. Ale w dalszym ciągu jest to zbyt duża ilość kombinacji by móc to sprawdzić ręcznie dlatego rozglądam się za programikiem który by to ułatwił.

[Xitami]

Kod: Zaznacz cały

Elay(N)={
	p=sqrtint(N);
	if(p*p==N, return(p));
	p=p+1;r=p*p-N;
	n=1;
	while(n*(n+1)<r,
		a=n*(n+1);
		b=r-a;
		x=b*b-r; y=2*(p-b);
		if(x>=y && x<=N,
			if(x%y==0,return(p-b));
		);
		n++
	);
	0
}

Elay(679)

[Elayne]

Dzięki za pomoc

[Xitami]

Dzięki za pomoc

Tylko tyle, a myślałem że zapytasz czemu to tak, a tamto owak, że to zrobiłem źle bo nie zrozumiałem i jak to poprawić.
A tu masz, tylko "dzięki"
na ile zrozumiałem to chyba jednak nie zadziała

[Elayne]

Na błędach się człowiek uczy Patrząc na listing zrozumiałem jak można w arkuszu kalkulacyjnym dodać możliwość podzielenia dużej liczby (do 1k cyfr) i otrzymać wynik w "normalnej" postaci (np: 24545...) a nie jako np: 2,23018644E+473 - czego mi bardzo brakowało. Wynik dzielenia będzie w podobnej formie jak mam przy np. mnożeniu: Do wczoraj mogłem takie liczby tylko dodać, odjąć lub pomnożyć a dzisiaj mogę tez podzielić, jestem o kolejny krok dalej. Brakuje jeszcze możliwości wyciągnięcia pierwiastka kwadratowego z danej liczby ale to można wygodnie zrobić na stronie internetowej: - wklej i kopiuj.

Wersja bez sprawdzania warunków, na skróty wygląda jak poniżej (nie widać zależności - „Kto chodzi na skróty ten w domu nie nocuje." ,przyslowie):
f = 679 // liczba faktoryzowana;
p = 27 // pierwiastek z 679=26,57 odrzucamy resztę po przecinku i dodajemy 1;
r = 50 // reszta, \(\displaystyle{ p^{2}-f}\) ( \(\displaystyle{ 27^{2}-679=50}\))
z = 5 // zmienna,

Podstawiamy to do tego równania:
\(\displaystyle{ (-r+(r-z(1+z))^{2})/(2(p-r+z(1+z)))}\) //w tym przykładzie otrzymamy 25
- wynikiem jest liczba całkowita dodatnia to podstawiamy dane do równań poniżej:
a=p-r+z(1+z) // wynik - 7
b=f/a // wynik - 97
Rozwiązanie:
a*b=f // 7*97= 679

na ile zrozumiałem to chyba jednak nie zadziała

I tak, i nie gdyż jest to podzbiór pewnej koncepcji. Jest to poprawne rozwiązanie dla ściśle określonego zbioru liczb.

[Xitami]

a w PARI piszesz x/y i masz
tysiąc cyfr, czy milion

[Elayne]

Do jednego tysiąca cyfr, co w zupełności wystarcza do zabawy. Ograniczeniem są tu możliwości programu - np. IBM Lotus Symphony już przy wczytywaniu arkusza dostaje zadyszki.