rozłożenie iloczynu liczb pierwszych

lightinside · Post autor: **lightinside** » 23 kwie 2014, o 19:44

Mam wdzięczną liczbę:

10403

Jest ona iloczynem pewnych dwóch liczb pierwszych, jak obliczyć których?

Tak mogę podstawiać pokoleji i patrzeć ale eeee wolę inaczej... ta metoda ma małą efektywność przy tak dużych liczbach...

(35 zgadłam mimo że ta metoda mi się nie podoba ale przy tak dużych wolę ludzką metodę)

a4karo · Post autor: **a4karo** » 23 kwie 2014, o 19:52

Czy mamy wnioskowac z tego, że 35 jest dzielnikiem? Chyba nie...

Tutaj akurat dużo sprawdzać nie trzeba; wystarczy sprawdzić liczby pierwsze <102.

musialmi · Post autor: **musialmi** » 23 kwie 2014, o 21:06

Akurat tak się tutaj zdarza, że 101 i 103 to odpowiedź Ale tak, jedna zawsze będzie mniejsza lub równa pierwiastkowi kwadratowemu tej liczby (co jest dość oczywiste). Ludzką metodą jest napisać program komputerowy, który to obliczy.

a4karo · Post autor: **a4karo** » 23 kwie 2014, o 21:45

W tym konkretnym przypadku mozna się troche pobawić:
\(\displaystyle{ 10403=10000+2\cdot 200+4-1=(100+2)^2-1=101\cdot103}\), ale generalnie nie ma prostej metody na rozkładanie liczb na czynniki.
Dzięki temu skuteczne są (na razie) metody kryptograficzne takie jak algorytm RSA.
Polecam książkę Simona Singha pt. Ksiega szyfrów.

virtue · Post autor: **virtue** » 23 kwie 2014, o 22:54

a4karo pisze:Czy mamy wnioskowac z tego, że 35 jest dzielnikiem? Chyba nie...

Tutaj akurat dużo sprawdzać nie trzeba; wystarczy sprawdzić liczby pierwsze <102.

powiedziałbym nawet, że <101

a4karo · Post autor: **a4karo** » 23 kwie 2014, o 22:59

virtue pisze:
a4karo pisze:Czy mamy wnioskowac z tego, że 35 jest dzielnikiem? Chyba nie...

Tutaj akurat dużo sprawdzać nie trzeba; wystarczy sprawdzić liczby pierwsze <102.
powiedziałbym nawet, że <101

Jak widzisz, <101 nie wystarczy, bo najmniejszym dzielnikiem pierwszym jest wlasnie 101

lightinside · Post autor: **lightinside** » 23 kwie 2014, o 23:20

musialmi, Nie sądze aby na kolokwium pozwolił korzystać z komputerów

Miałam na myśli, że dla 35 znalazłam że to 5 i 7 tak wypisując sobie pierwsze i dopasowując.

"Dzięki temu skuteczne są (na razie) metody kryptograficzne takie jak algorytm RSA."

Dokładnie o to chodzi możliwe że da n i na tej podstawie muszę mieć p i q aby móc coś zrobić...

Właśnie rozszyfrować za szyfrować etc...

Oczywiście na kartce...

a4karo · Post autor: **a4karo** » 23 kwie 2014, o 23:26

na kolokwium (czyli bez wyspecjalizowanych programow) pozostaje Ci kartka i ołówek, lub kalkulator, jeżeli wolisz.

virtue · Post autor: **virtue** » 23 kwie 2014, o 23:47

Tak zauważylem, źle wskoczylo mi w kalkulatorze, nie zdazylem usunac postu