|
Bill Allombert on Fri, 06 Jun 2025 21:32:20 +0200
|
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
|
Re: finding primes modulo which x^m mod f(x) has a prescribed result
|
- To: Max Alekseyev <maxale@gmail.com>
- Subject: Re: finding primes modulo which x^m mod f(x) has a prescribed result
- From: Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>
- Date: Fri, 6 Jun 2025 21:32:16 +0200
- Cc: pari-users@pari.math.u-bordeaux.fr
- Delivery-date: Fri, 06 Jun 2025 21:32:20 +0200
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/simple; d=math.u-bordeaux.fr; s=2022; t=1749238338; bh=XNCXDxgGLx5+JegIotTQc7iZUWOswxiRjfcZX7OkUwE=; h=Date:From:To:Cc:Subject:References:In-Reply-To:From; b=HNj5jkyEpSRH6PSqpXFhHKYQ9C7DmWX1gNLJfJdWUF1MKpMonpzc5tb7PTtQD4tz5 GI+OryuZ8DvFRUmnYKKtzIf8HcOMQKGce3OgKRFGxjKc3mnBxmST2Wix4Mb1ooxhj4 edf4jk4fw2RF/H/orOVWshy8MbRmoTOSzMeOvEzS2p+3ug1LuKGPqYtD/CQ3/rhPXR N4TJO6cySlDiG4/QBlrsygSLjccRlCBSjCwyqnCWQvHBcvnC3p1TD3YmJZ+3dnVC4B o/hepA+pBgVwWxt5bssK0k4w7TdItcbCjTQHklk9vydAKpezZu59g4/PtvxdrdANhM G/kAIbx0uESQ3aqOvHixwbPDuafiTscooun2HJ/Mu0/AE77UHbSO0JqOaEVMuxFC8c XheVD1uhMBbpqA1aOk+zeVRzU9h/CO62yEGFrrlyhyygk22BLOdALQfKyBPD+zTASM knTUIv7cwChMgKufv67L6MdjSmStHWr1RUzxn7kgRvSABc8J2aRqWISrIBkXpNQvL9 u3PR5XCC36iKxhkbW6csLcHkhRj2ZZ3bqvrdUhRhgz7BnQNZ8oIxyXoje+Ez9AKJSE QB7r0WZU0qnRV8zZP1CmRG2ph7OyVFI3o92VtmG2gtZHhyxotWeDx3Iy8+iRGPGQcL wthQ5XWWNJp4XMJrVar+i6zA=
- In-reply-to: <CAJkPp5M0d1kpbP7SewJp6DmyH2zwJCaTEsAcE=zfA+JX0ZzD9A@mail.gmail.com>
- Mail-followup-to: Max Alekseyev <maxale@gmail.com>, pari-users@pari.math.u-bordeaux.fr
- References: <CAJkPp5MJ5G9y=pGAjnas3-=KsYQKAfoo+-rVPqeS6yX1K-2auA@mail.gmail.com> <aEAZMhKUuuMMso94@seventeen> <CAJkPp5PV1yCoEDU-PrmHeaQqjq-tRkAq2n-15w0DzYND3TD2Lg@mail.gmail.com> <aECOT3cFnXuaFjBK@seventeen> <CAJkPp5M0d1kpbP7SewJp6DmyH2zwJCaTEsAcE=zfA+JX0ZzD9A@mail.gmail.com>
On Wed, Jun 04, 2025 at 03:44:11PM -0400, Max Alekseyev wrote:
> Hi Bill,
>
> First off, I should have said that I'd like to have O(poly(log(m)))
> not O(log(m)) algorithm, but even with my honest typo, I don't quite follow
> how your exercise implies the absence of the algorithm with O(log(m)) space.
> >From m = p-1 (mod p^2-1), it follows that p <= m+1 and so it fits the
> O(log(m)) space (if it was the size of p you referred to).
>
> Anyway, I'd like to have the algorithm be bounded in both time and memory
> resources by a polynomial in log(m), not in m itself.
If you only need m = 10^k then it might possible to prove the content
is always 4 for k>=2.
Cheers,
Bill.