|
Karim Belabas on Sat, 12 Oct 2024 18:08:20 +0200
|
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
|
Re: computing all square root modulo a composite
|
- To: Max Alekseyev <maxale@gmail.com>, Pari Users <pari-users@pari.math.u-bordeaux.fr>
- Subject: Re: computing all square root modulo a composite
- From: Karim Belabas <Karim.Belabas@math.u-bordeaux.fr>
- Date: Sat, 12 Oct 2024 18:08:16 +0200
- Delivery-date: Sat, 12 Oct 2024 18:08:20 +0200
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/simple; d=math.u-bordeaux.fr; s=2022; t=1728749298; bh=lk92Yn/rC/akXcwjHem+1vQ/hOhLzfrZipsNZfvj0tI=; h=Date:From:To:References:In-Reply-To:From; b=XKSKEd0tDL7OQHq2Sl3rjLUV/7jZYv41UnaZACWQb47WyDSoxmu2/QKJ9MLrv9mjG x7/pZ4oj/eYiYyUBohWieLdp+UtXp07yZ/8Rgut2GAPkFoZv3gNiaQ9mz2ke+KV7DK 9PtdRcLF7MISBX7yvjE/Qz7wVfJ+mvkBmPz5L9w+vH5r3YwnLRWtR6xYQ3LAvqKPyU 4tMF4LSYt5CO9T6bv/W5oX7VoEYP8C796KUY0gXAknkZHfKHZockzwSLvA2L/vQgTo Sv0wNjFCxiIE2SlhoEGN1GH4EZ4qmhMwgHs0OBpx772GendKYZf0DOu78oF17sT0QJ zbcZxO7CCeVT0E/0mqAGqHrfF+b3by3D5mMMFdWuoPej4LZBGWvPeLiUUzEbV16k2o qSi5RaHElkm5QYdHGIfb+Dc9ZYQJzF9xVc5KcVPZ3J8XEzAtehbxb8kyOiXzWHnfwt vMGpYu2sTLVXilKARsLOllTFn/hDt6HLtM2S/Efe19P6tcRwJKihMnbkqi28f8Aky2 C8oe57dFRIfvfx8Wx6earUXbAQ3MIYnczkRi3UiCzxqyqf61NTFvv+Bv8inI/In3Gm lWGubfbYfLsEmecYF0TxmUrjpHRrFOtuey0fK0aUbmMTXwIgo/HB274uAkcZ1tMRuE SiG1d1ApVWO3AyZSwjBrJJlg=
- In-reply-to: <ZwqeQYeuDsDxZLZT@math.u-bordeaux.fr>
- Mail-followup-to: Max Alekseyev <maxale@gmail.com>, Pari Users <pari-users@pari.math.u-bordeaux.fr>
- References: <CAJkPp5PxxVZHXM02kNfJf1aV0CYdRoBgZ5YkKNvHbHF4yCXHqw@mail.gmail.com> <ZwqYkqFSUNZekIwn@math.u-bordeaux.fr> <Zwqa0UPT2UxgtaEQ@seventeen> <CAJkPp5M8u0a7fP-bZURFDckB+KkcrocpcYSx=NhSD-OaueuxgA@mail.gmail.com> <ZwqeQYeuDsDxZLZT@math.u-bordeaux.fr>
* Karim Belabas [2024-10-12 18:05]:
> * Max Alekseyev [2024-10-12 17:56]:
> > As for the name, maybe sqrtall() ?
>
> sqrtmod rather. Also note that function gives you all roots of any
> monic quadratic polynomial, not only square roots.
>
> And it has a weird output format, which makes perfect sense if you
> think of it (you get the most precise mathematical information). It
> does not give you all solutions mod N but modulo M | N, whose
> lifts + k (N/M) mod N, 0 <= k < M are the solutions mod N.
Rather:
lifts + k M mod N, 0 <= k < N/M are the solutions mod N.
Cheers,
K.B.
--
Pr. Karim Belabas, U. Bordeaux, Vice-président en charge du Numérique
Institut de Mathématiques de Bordeaux UMR 5251 - (+33) 05 40 00 29 77
http://www.math.u-bordeaux.fr/~kbelabas/