Wśród operacji arytmetycznych występuje taka, że iloczyn dwu liczb jest obcinany do reszty z dzielenia przez jakąś wartość. Czyli brany modulo.
Czy mając dane taki iloczyn oraz jeden z czynników, możemy wyznaczyć drugi? Odpowiedź jest twierdząca, a nawet łatwa do wyznaczenia, chociaż w ogólności moze być niejednoznaczna - może być więcej wartości, które przycięte dadzą tę samą wartość iloczynu.
Przykład liczbowy, Iloczyn 65*x = 175 (mod 1000). Czyli należy podzielić 175 / 65 w liczbach całkowitych modulo 1000.
Zapiszmy 1000 w systemie o podstawie 65: 1000 = 15*65+25.
Teraz, aby uzyskać wartość podzielną przez 65, należy dodać tyle tysięcy, by uzyskana wartość była podzielna przez 65. Szukamy k, by
175 + (25*k)
było wielokrotnością 65.
Szybko znajdujemy, że współczynnikiem k jest 6, czyli 6*1000+175 = 6175 jest wielokrotnością 65, dokładniej 6175 = 65*95.
Znaleźliśmy: 175 / 65 = 95 (mod 1000). Dzielenie przeszło na dodawanie i sprawdzanie podzielności, co zapisane w systemie znanego dzielnika sprowadza się tylko do dodawań i przeniesień...
Brak komentarzy:
Prześlij komentarz