|
TwojePC.pl © 2001 - 2024
|
 |
A R C H I W A L N A W I A D O M O Ś Ć |
 |
| |
|
[Algorytmika - Kryptografia] Faktoryzacja liczb Całkowitych , Mackie Messer 3/02/04 23:47
Witam. Jak w temacie. Poszukuje gotowych rozwiązan badz materiałów, ktore pomaga mi zrozumiec i skonstruowac rozwiazanie mojego problemu. Temat zadania:
"Dla najdłuższej z reprezentacji liczb całkowitych w dowolnym języku programowania, nie krótszej jednak niż 32 bity (np. typ unsigned long w języku C) proszę przeanalizować zależność czasu potrzebnego na faktoryzację liczby całkowitej N od wartości tej liczby. Badanie to winno obejmować co najmniej dwa algorytmy faktoryzacji. "
Z gory dzieki za linki czy hinty. Pozdrawiam."Predzej sam siebie zgasze, niz sie wypale"
F. Nietzsche - eee , Birdman 3/02/04 23:53
a co to jest faktoryzacja??ping? - A tam linki. Od razu uderzaj , Agnes 4/02/04 00:02
na priv do akustyka.Metafizyka: - Poznaj, proszę, to jest
Fizyk, a to jego Meta... - najprosciej: , Mackie Messer 4/02/04 00:03
Faktoryzacja danej liczby x to znajdowanie takich liczb powiedzmy z i y aby ich iloczyn byl rowny x
x = z*y"Predzej sam siebie zgasze, niz sie wypale"
F. Nietzsche - hmm , akustyk 4/02/04 01:28
1. metoda "trywialna" - czyli sprawdzenie od 1 do sqrt(N).
tu oszacowanie zlozonosci nie jest trudne. w ramach przyspieszenia mozna skorzystac z sita Erastotenesa, a ze gestosc liczb pierwszych w przedziale 1...K jest asymptotycznie log(K)/K, to i zlozonosc jest istotnie mniejsza (bo K = sqrt(N)).
ta metoda sprawdza sie tak naprawde pierwszosc. przy stwierdzeniu zlozonosci liczby robi sie jej rozklad a potem powtarza algorytm dla czynnika. i tak sie powtarza dopoki jest co rozkladac. oczywiscie, rozsadna realizacja tego wariantu musi uwzglednic kilka trikow i dosc duze zuzycie pamieci.
2. sa troszke bardziej skomplikowane metody, ktorych podwalin matematycznych nie za bardzo rozumiem (przynajmniej nie wszystki). wal na google i szukaj takich algorytmow: Pollard's Rho, Quadratic Sieve, Number Fields Sieve. to ostatnie tlumaczy sie bodajze jako przesiewanie w polu liczbowym. reszta chyba jasna. jak znajdziesz opis algorytmu, to oszacowania beda od razu dane.
pozdr!http://akustyk.magma-net.pl - dziekuje :) , Mackie Messer 4/02/04 01:40
Jutro rano sprobuje ogarnac umyslem to co napisales i zaimplementowac. Tylko co na to moj kompilator... :)
Pozdrawiam."Predzej sam siebie zgasze, niz sie wypale"
F. Nietzsche
- sprawdz maila , ksiaze 4/02/04 09:08
masz tam troche stuffu- dostalem :) , Mackie Messer 4/02/04 16:04
dzieki jeszcze raz."Predzej sam siebie zgasze, niz sie wypale"
F. Nietzsche
|
|
|
|
 |
All rights reserved ® Copyright and Design 2001-2024, TwojePC.PL |
 |
|
|
|
