Ru.Wikipedia.Org - Обсуждение:Алгоритм Гельфонда

Меню
Главная
Случайная статья
Настройки

Обсуждение:Алгоритм Гельфонда — Шенкса
Материал из https://ru.wikipedia.org

вопрос по алгоритму

почему в статье в пункте 3.2. алгоритма используется

\gamma

\gamma

•

\alpha ^{m}

, а не

\gamma

\gamma ^{i}

?

dickson's work on tonelli says the algorithm will work on mod p^k

I'm not a professional mathematician but I just read Dickson's "History of Numbers" ^[1] where it says on page 215 that

A. Tonelli^[2] gave an explicit formula for the roots of

x^{2}=c({\bmod {p^{\lambda }}})

Perhaps some mathematician should work out if the Tonelli algorithm takes modular square roots for powers of primes as well as for primes This Wiki article says the algorithm only works for prime modula.

After reading the Dickson text a couple of times on p215,216 I came across this formula for the square root of

x^{2}{\bmod {p^{y}}}

when

p=4*7+1

, or

s=2

and

A=7

for

x^{2}{\bmod {p^{\lambda }}}\equiv c

then

x{\bmod {p^{\lambda }}}\equiv \pm (c^{A}+3)^{\beta }*c^{(\beta +1)/2}

where

\beta \equiv a*p^{\lambda -1}

Noting that

23^{2}{\bmod {29^{3}}}\equiv 529

and noting that

\beta =7*29^{2}

then

(529^{7}+3)^{7*29^{2}}*529^{(7*29^{2}+1)/2}{\bmod {29^{3}}}\equiv 24366\equiv -23

So Tonelli's math does seem to take modular square roots of prime powers!

Here's another equation:

2333^{2}{\bmod {29^{3}}}\equiv 4142

and

(4142^{7}+3)^{7*29^{2}}*4142^{(7*29^{2}+1)/2}{\bmod {29^{3}}}\equiv 2333

On page 215-216 of the Dickson book, the equation is given of Tonelli's:

X{\bmod {p^{y}}}\equiv x^{p^{y-1}}*c^{(p^{y}-2p^{y-1}+1)/2}

where

X^{2}{\bmod {p^{y}}}\equiv c

and

x^{2}{\bmod {p}}\equiv c

;

Using

p=23

and using the modulus of

p^{3}

the math follows (in mathematica):

Mod[1115^2, 23 23 23]=2191
 
Mod[1115^2, 23]=6
PowerMod[6, 1/2, 23]=11

Mod[11^(23 23) 2191^((23 23 23 - 2 23 23 + 1)/2), 23 23 23] =1115

Thus Tonelli's work can work for a 3 mod 4 prime power.

Endo999 (обс.) 23:33, 31 января 2018 (UTC)[ответить]

@Endo999: this seems unrelated to Baby step-giant step algorithm, why did you post it here? adamant.pwn — contrib/talk 02:10, 18 января 2020 (UTC)[ответить]

I don't recall posting, if I did, sorry. It definitely belongs on the tonelli-shank modular square root article

"History of the Theory of Numbers" Volume 1 by Leonard Eugene Dickson, p215 url=https://ia800209.us.archive.org/12/items/historyoftheoryo01dick/historyoftheoryo01dick.pdf
"AttiR. Accad. Lincei, Rendiconti, (5), 1, 1892, 116-120."