🚀 go-pugleaf

paasivir@jyu.fi (Risto Paasivirta) writes:
>Satunnaishakkeroinnilla ja mutu-logiikalla loysin sellaisen testin
>signaturelle s, etta jos J(s mod p,p) = J(s mod q,q) = 1, niin s on
>jokin nelio mod pq. (J(a,p) = Jacobi symbol, 1 if a does not divide
>p evenly and a is a quadratic residue mod p, 0 if a divides p evenly,
>-1 if a does not divide p evenly and a is not a quadratic residue of
>p.) Nopea testi, mutta onko tuossa jarkea?

Et varmaan mutu-tekniikalla l|yt{nyt Jacobin symbolia... Seuraava
yht{l| on voimassa (p,q parittomia positiivisia kokonaislukuja):

J(s,q)*J(s,p)=J(s,p*q)

eli jos s:n Jacobin symboli p:lle ja q:lle pysyy ykk|sen{, niin s=r^2
(mod pq).

>Jos s:sta aluksi jattaa muutaman alimman bitin nollaksi, ja valitsee 
>pienimman s+n:n joka on jokin nelio, niin yksiselitteisen allekirjoi-
>tuksen tekeminen on mahdollista. Eika mitenkaan hidasta.

Miten viestin vastaanottaja verifioi viestist{, ett{ viestin l{hett{j{
on juuri se, jolta viesti n{ytt{{ tulleen? (allekirjoitus)

Pauli Wihuri

Ps. Teetk| jotain opinn{ytett{?