[Algorytmika - Kryptografia] Faktoryzacja liczb Całkowitych

	B O A R D
	» Board » Zadaj pytanie » Archiwum » Szukaj » Stylizacja

M E N U

» Nowości

» Archiwum

» Recenzje / Testy

» Board

» Rejestracja

Szukaj @ TwojePC

	OBECNI NA TPC
	» ligand17 09:44 » Markizy 09:44 » Robek 09:41 » ARTi 09:40 » Sherif 09:32 » Sociu 09:28 » jablo 09:27 » rrafaell 09:13 » wrrr 09:11 » ProSavage 09:06 » maddog 09:01 » KHot 08:59 » Syzyf 08:59 » b0b3r 08:52 » rooter666 08:51 » XepeR 08:49 » MARtiuS 08:48 » DJopek 08:34 » Artaa 08:33 » emigrus 08:33 Dzisiaj przeczytano 41141 postów, wczoraj 25974 Szybkie ładowanie jest: włączone.

ccc

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
1. 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
1. dostalem :) , Mackie Messer 4/02/04 16:04
  dzieki jeszcze raz.
  "Predzej sam siebie zgasze, niz sie wypale"
  F. Nietzsche