Pokazać, że z szansą co najmniej 50 procent
: 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?
Jak to zrobić? Może mi ktoś pomóc?