Pokazać, że z szansą co najmniej 50 procent

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
max123321
Użytkownik
Użytkownik
Posty: 2733
Rejestracja: 26 maja 2016, o 01:25
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 812 razy

Pokazać, że z szansą co najmniej 50 procent

Post autor: max123321 » 3 maja 2021, o 18:16

Pokazać, że z szansą co najmniej \(\displaystyle{ 50}\) procent możemy przy losowym wyborze \(\displaystyle{ b}\) i \(\displaystyle{ c}\) modulo \(\displaystyle{ n}\) spełniających warunek \(\displaystyle{ b^2=c^2 \mod n}\), znaleźć nietrywialny dzielnik \(\displaystyle{ n}\) stosując algorytm Euklidesa do obliczenia \(\displaystyle{ NWD(n,b+c)}\) i \(\displaystyle{ NWD(n,b-c)}\).

Jak to zrobić? Może mi ktoś pomóc?
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

ODPOWIEDZ