Re: a=x^b mod p, solvable?
From: Phil Carmody (thefatphil_demunged_at_yahoo.co.uk)
Date: 11/15/04
- Next message: PhDs.org Webmaster: "New mathematics/physical sciences positions at http://jobs.phds.org, November 15, 2004"
- Previous message: kalikinkar: "Re: Student Teacher Looking for Resources"
- In reply to: Chu: "a=x^b mod p, solvable?"
- Messages sorted by: [ date ] [ thread ]
Date: 15 Nov 2004 11:47:49 +0200
kssarh@hotmail.com (Chu) writes:
> Hello all, quick algebra question that is bothering me. Given a=x^b
> mod p, where a, b, and p (prime) are known, and it is known that a
> solution exists, is there an easy way to solve for x?
For a general-purpose and fairly swift solution, use Cantor-Zassenhaus.
Special cases of b (such as |b|<=2) can be done more swiftly using Tonelli-Shanks.
Special cases of b/p pairs for |b|>2 can also be done more swiftly using FlT.
Phil
-- They no longer do my traditional winks tournament lunch - liver and bacon. It's just what you need during a winks tournament lunchtime to replace lost ... liver. -- Anthony Horton, 2004/08/27 at the Cambridge 'Long Vac.'
- Next message: PhDs.org Webmaster: "New mathematics/physical sciences positions at http://jobs.phds.org, November 15, 2004"
- Previous message: kalikinkar: "Re: Student Teacher Looking for Resources"
- In reply to: Chu: "a=x^b mod p, solvable?"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
