mersenneforum.org > Math Breaking a prime p into a^2 + 3* b^2
 Register FAQ Search Today's Posts Mark Forums Read

 2009-08-25, 07:32 #1 SPWorley   Jul 2009 31 Posts Breaking a prime p into a^2 + 3* b^2 I'm playing with cubic reciprocity formulas. From that link, it states "A theorem of Fermat states that every prime p ≡ 1 (mod 3) is the sum of a square and three times a square: p = a^2 + 3b^2" How would you go about finding a and b given p? Is there a better strategy than brute force, iterating b=1, b=2, b=3, b=4.. etc and seeing if the remainder (p-3*b^2) is a square? There are efficient square-detecting routines, but even if they're cheap, you could be iterating up to sqrt(p) times! How about the case where p=a^2 +2* b^2, which comes up when dealing with quartic reciprocity? Last fiddled with by SPWorley on 2009-08-25 at 07:32
2009-08-25, 09:46   #2
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by SPWorley I'm playing with cubic reciprocity formulas. From that link, it states "A theorem of Fermat states that every prime p ≡ 1 (mod 3) is the sum of a square and three times a square: p = a^2 + 3b^2" How would you go about finding a and b given p? ]

Factor p over Q(sqrt(-3)). See H. Cohen's book on Algebraic Number Theory.
I believe that a variation of Cornachia'a algorithm is used, but my memory
could be faulty. It's been a long time since I looked at this kind of stuff.

2009-08-25, 12:08   #3
Gammatester

Mar 2009

468 Posts

Quote:
 Originally Posted by SPWorley How about the case where p=a^2 +2* b^2, which comes up when dealing with quartic reciprocity?
Cornacchia's algorithm can be used in this case too, generally you can solve a^2 + d*b^2 = p, with 0<d<p. There is a modified algorithm for a^2 + |d|*b^2 = 4p. Crandall/Pomerance: Prime Numbers (Algorithm 2.3.12 +) is another reference.

 2009-08-26, 03:05 #4 SPWorley   Jul 2009 111112 Posts Thanks very much for the references.. it's all there in Crandall/Pomerance. Pretty straightforward, too! I appreciate it.

 Similar Threads Thread Thread Starter Forum Replies Last Post jasong Lounge 71 2013-10-15 03:39 ewmayer Soap Box 11 2013-06-06 06:15 emily PrimeNet 3 2013-03-01 05:49 roger Information & Answers 13 2007-11-17 06:50 jflin Hardware 8 2007-09-06 08:25

All times are UTC. The time now is 08:30.

Sat May 28 08:30:40 UTC 2022 up 44 days, 6:31, 0 users, load averages: 1.15, 1.27, 1.42