Dzielenie, gdy iloczyn jest obcięty modulo

 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ń...

Pierwiastek kwadratowy z dużych liczb, różne podejścia algorytmów

Problem obliczania pierwiastka kwadratowego oraz zwrotu wartości całkowitej został zaproponowany na portalu GeeksForGeeks 12 sierpnia 2025 roku. Zaproponowano 4 algorytmy: naiwny z mnożeniem, wyszukiwanie binarne, oraz dwa korzystające z biblioteki wbudowanej, np. Python.math. 

Dołączyłem jeszcze dwa swoje: naiwny z dodawaniem +=(2p+1), wspomniany miesiąc temu przy podawaniu złożoności wielomianowego algorytmu faktoryzacji, oraz jego rozwinięcie wykorzystujące fakt, że każdy kwadrat mozna zapisać jako 1 0 0 w systemie o pewnej podstawie p. Kod ostatniego niemiły, zaczyna działać dopiero dla wartości większych niż 100 w systemie dziesiętnym.
10*p + k, gdzie k wyznaczane z krotności możliwości konwersji przycięcia liczby N_p -> N_{p+k} do odpowiedniej długości względem p, jedna cyfra p na dwie cyfry z N = N[n]...N[1] N[0] w dziesiętnym
2p+1 < 100*reszta+10*N[b+1]+N[b]

Użyłem bardzo dużej liczby: 27997833911221327870829467638722601621070446786955428537560009929
26128400107609345671052955360856061822351910951365788637105954482
006576775098580557613579098734950144178863178946295187237869221823983

Algorytmy miały działać w parę sekund - tego testu naiwe nie przeszły.
Te, które w teorii były najszybsze, złożoności stałej O(1) zarówno pamięci jak i czasu, czyli
int(math.sqrt(n))
int(math.exp(0.5*math.log(n)))
podały błędne wyniki -- wystąpiła propagacja błędu obliczeń liczb zmiennoprzecinkowych, uzyskałem np. wartość
52912979420196447 944286770683838014
89465575494900455707262162396795715834972575453540520946581897216
Na portalu wspomniano, że wynik może być niezbyt dokładny, dokładniej nieco zaniżony. A okazał się znacznie zawyżony.

Poprawny wynik dały zaledwie dwa algorytmy z sześciu bez czekania:
52912979420196447 553235400217339415 00571661886712719898054010160087776775983652376577898717296799172

Zgodność z 'najszybszym' tylko na siedemnastu cyfrach dziesiętnych. 

Jak to trzeba sprawdzać zakres stosowania bibliotek...