Napisałem dzisiaj skrypt ułatwiający faktoryzację wyniku mnożenia dwóch liczb pierwszych (testowany na czynnikach różnych od siebie, większych niż 11 i mniejszych niż 179). Wygenerowane kolejne cyfry po przecinku należy sumować po kolei (0.31662479035539980998237297171726822853088378906 i dodajemy 3+1, 3+1+6 ), wynotować liczby pierwsze, sprawdzić wynotowane liczby, jeżeli żadna nie daje zadowalającego wyniku dzielenia z liczbą na wejściu, należy sprawdzić też sąsiadujące liczby (np. mamy wynotowaną liczbę 13 to sprawdzamy też 11 i 17).
Zamiast sprawdzania kolejnych liczb pierwszych po kolei, zawężamy dzięki temu liczbę możliwości do n*3 (n - wynotowane liczby).
Kod skryptu napisany w języku Ruby (można przetestować w przeglądarce np. pod adresem: ):
n = 47
puts "Podaj wynik mnozenia 2 liczb pierwszych z dopiskiem .0 na końcu:"
a = gets.to_i
b = Math.sqrt(a)
c = a / b.round
d = b - c
printf("Wynik: %.#{n}f",d)
Ostatnio zmieniony 10 maja 2010, o 09:36 przez xanowron, łącznie zmieniany 1 raz.
Powód:Temat umieszczony w złym dziale.
Pierwsza sprawa, co to za algorytm rozkładu na czynniki, na jakiej zasadzie on działa? Z tak wąskim przedziałem stosowania, nie jest zbyt użyteczny, sprawdzenie wszystkich liczb pierwszych będzie trwać ułamek sekundy, czemu ma służyć ten skrypt? Dodaj chociaż do niego te operacje o których mówisz - sumowanie cyfr po przecinku i tak dalej, niech chociaż poda na wyjściu te czynniki.
Chodzi o rozłożenie na czynniki podanej liczby, liczby która w domyśle powstała jako iloczyn dwóch liczb pierwszych. Iloczyn dużych liczb pierwszych służy do tworzenia klucza w popularnych algorytmach szyfrowania, sposób szybkiego rozkładu (faktoryzacji) takiego iloczynu wykluczyłby z użycia te algorytmy. Tyle, że liczby pierwsze używane do generowanie klucza są naprawdę duże, ich iloczyn sięga kilkuset znaków, stąd moje zdziwienie warunkami na jakich działa ten program i finezją algorytmu, zakładając, że działa.
Dzięki za informację .
A tak na serio to moje pytanie retoryczne miało podkreślić jaki problem kolega chce rozwiązywać i do jakiej klasy należy ten probelm. Nie chcę jakoś podcinać skrzydeł koledze niech zaprezentuje swój pomysł do końca w rozbudowanej formie. Poproszę więc o pełen algorytm i ewentualnie dowód poprawności(i o ile przyspiesza wyszukiwanie bo narazie wniosukję, że jest to oparte na jakiejs magicznej liczbie) - oczywiście jak nie potrafisz przeprowadzic dowodu to podaj sam algorytm, ale w rzetelnej formie. Pozdrawiam
Nie jestem matematykiem, eksperymentowałem z liczbami i znalazłem ciekawą zależność, którą chciałem się podzielić. Prawdopodobnie coś w tym stylu zostało już odkryte wcześniej (zbyt proste żeby ktoś tego wcześniej nie wymyślił).
Podałem liczby z zakresu który testowałem i rzeczywiście to działa. Czy ten algorytm do czegoś się przyda, tego nie wiem. Na pewno może posłużyć do zawężenia zakresu poszukiwanych liczb pierwszych, później pozostaje brute-force (chyba że istnieją dodatkowe zależności o których nie wiem).
Przykład podany w pierwszym poście był dla liczby 11, podam za chwilę parę przykładów dla pomnożonych 2 liczb pierwszych, zakres który podaje jest spowodowany określoną liczbą miejsc po przecinku.
Nie jestem matematykiem, eksperymentowałem z liczbami i znalazłem ciekawą zależność, którą chciałem się podzielić. Prawdopodobnie coś w tym stylu zostało już odkryte wcześniej (zbyt proste żeby ktoś tego wcześniej nie wymyślił).
Podałem liczby z zakresu który testowałem i rzeczywiście to działa. Czy ten algorytm do czegoś się przyda, tego nie wiem. Na pewno może posłużyć do zawężenia zakresu poszukiwanych liczb pierwszych, później pozostaje brute-force (chyba że istnieją dodatkowe zależności o których nie wiem).
Przykład podany w pierwszym poście był dla liczby 11, podam za chwilę parę przykładów dla pomnożonych 2 liczb pierwszych, zakres który podaje jest spowodowany określoną liczbą miejsc po przecinku.
1219 wynik: 0.91418050019218100032958318479359149932861328125
Obliczenia: 9+1+4+1+8=23
Wynik dzielenia: 1219/23=53 (53 jest liczbą pierwszą)
4559 wynik: 0.52036729757918465111288242042064666748046875000
Obliczenia:
1. 5+2=7 4559/7=651 (651 nie jest liczbą pierwszą)
2. 5+2+3+6+7=23 4559/23=198,22
3. 5+2+3+6+7+2+9+7=41 4559/41=111,195
4. 5+2+3+6+7+2+9+7+5+7=53 4559/53=86,02
5. 5+2+3+6+7+2+9+7+5+7+9+1+8=71 4559/71=64,21
6. 5+2+3+6+7+2+9+7+5+7+9+1+8+4+6+5+1+1+1=89 4559/89=51,22
7. 5+2+3+6+7+2+9+7+5+7+9+1+8+4+6+5+1+1+1+2+8+8=107 4559/107=42,61
8. 5+2+3+6+7+2+9+7+5+7+9+1+8+4+6+5+1+1+1+2+8+8+2=109 4559/109=41,83
9. 5+2+3+6+7+2+9+7+5+7+9+1+8+4+6+5+1+1+1+2+8+8+2+4=113 4559/113=40,35
10. 5+2+3+6+7+2+9+7+5+7+9+1+8+4+6+5+1+1+1+2+8+8+2+4+2+4+2+6=127 4559/127=35,898
11. 5+2+3+6+7+2+9+7+5+7+9+1+8+4+6+5+1+1+1+2+8+8+2+4+2+4+2+6+4=131 4559/131=34,802
12. 5+2+3+6+7+2+9+7+5+7+9+1+8+4+6+5+1+1+1+2+8+8+2+4+2+4+2+6+4+6=137 4559/137=33,3
13. 5+2+3+6+7+2+9+7+5+7+9+1+8+4+6+5+1+1+1+2+8+8+2+4+2+4+2+6+4+6+6+6=149 4559/149=30,6
14.5+2+3+6+7+2+9+7+5+7+9+1+8+4+6+5+1+1+1+2+8+8+2+4+2+4+2+6+4+6+6+6+7+4+8+7+5=180 (liczba maksymalna)
Liczby sąsiadujące
Obliczenia:
7 - z poza zakresu, nie sprawdzam 5 i 11
1. 23 - 19, 29
4559/19=239,95
4559/29=157,21
2. 41 - 37, 43
4559/37=123,22
4559/43=106,02
3. 53 - 47, 59
4559/47=97 (97 - jest liczbą pierwszą 47*97=4559)
Przy wykorzystaniu wszystkich możliwości - ok. 29 kroki (obliczenie+sprawdzenie), sprawdzaniu 2 sąsiednich liczb pierwszych "w locie" - 11.
Metoda brute-force - 22 kroki (obliczenie+sprawdzenie).
puts "2 Liczby pierwsze:"
z = gets.to_i
y = gets.to_i
a = z * y
b = Math.sqrt(a)
c = a / b.round
d = (b - c) * (10**47)
e = Integer d
print(e)
Skrypt w takiej formie wystarczy do beta testów.
Nie sądzę żeby ktoś wpadł na tak kretyński pomysł jak wygenerowane klucza przy pomocy 2 takich samych liczb pierwszych (np. 41*41 ) lub leżących obok siebie np. 41 * 43 (program pokazuje wynik zaczynający się od 9), nie jest to wyznacznik tylko wskazówka dla poszukiwań np. 15472981 * 29 też pokazuje wynik zaczynający się od 9 ale już 15472981 * 3 nie - liczbę zaczynającą się od 1, można szukać tutaj zależności ale potrzebne są dane statystyczne).
Liczby biorę z tabelki: http://liczby_pierwsze.republika.pl/1000.html
Jakby komuś miało by się to przydać to skrypty są na licencji LGPL (v3)
AU
lgplv3-88x31.png (1.91 KiB) Przejrzano 156 razy
a pomysł na licencji Creative Commons: Uznanie autorstwa 3.0 Polska
Witam,
Minęły już 3 lata od czasu kiedy opracowałem ten skrypt, myślałem że odkryłem Amerykę a nie bezużyteczną ciekawostkę. To było jeszcze kiedy byłem w liceum.
Anuluję licencję, którą i tak nikt by się nie przejmował jakby komuś byłoby to potrzebne.
Pozdrawiam,
Łukasz Fuszara
