Eli miten ratkaistaan seuraavasta (x, y, n)?
8346192 = (1193363x y) mod n,
6550593 = (8346192x y) mod n,
3632765 = (6550593x y) mod n
Tai, jos joku osaa sanoa ratkaisun, niin en ole erityisen kiinnostunut siitä, miten siihen päädytään.
8346192 = (1193363x y) mod n,
6550593 = (8346192x y) mod n,
3632765 = (6550593x y) mod n
Tai, jos joku osaa sanoa ratkaisun, niin en ole erityisen kiinnostunut siitä, miten siihen päädytään.
Vastaukset 5
Vanhimmat
Eikös olisi parempi laskea hieman pienimmillä numeroilla?
Sovitaan että:
a=(b Y) mod n
c=(d Y) mod n
e=(f Y) mod n
Y = a-b
tai
Y = -a-b
Y = c-d
tai
Y=-c-d
Y=e-f
tai
Y=-e-f
ja jatkappas tästä itse
Triviaali ratkaisu: n=1, x=0, y=0
Tällaisia ratkaisuja näyttäisi löytyvän:
(0,0,1)
(4,3,7)
(4,6,11)
(4,17,77)
(291,374,419)
(291,374,2933)
(4481,2888,4609)
(9090,12106,32263)
...
Ihan mielenkiinnosta kysyisin, millaisella algoritmilla etsit nuo ratkaisut? (Oletan, että pistit tietokoneen hommiin ja käytit jonkinlaista brute force -lähestymistapaa.)
Yhtälöistä voi eliminoida y:n, jolloin jäljelle jää kaksi yhden muuttujan yhtälöä. Ratkaise kumpikin Eukleideen algoritmilla ja tarkista, mitkä ratkaisut ovat yhteisiä molemmille.