20090825, 07:32  #1 
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 (p3*b^2) is a square? There are efficient squaredetecting 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 20090825 at 07:32 
20090825, 09:46  #2  
Nov 2003
16444_{8} Posts 
Quote:
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. 

20090825, 12:08  #3  
Mar 2009
38_{10} Posts 
Quote:


20090826, 03:05  #4 
Jul 2009
31 Posts 
Thanks very much for the references.. it's all there in Crandall/Pomerance.
Pretty straightforward, too! I appreciate it. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Grammar rulebreaking ftw  jasong  Lounge  71  20131015 03:39 
Breaking: US DOJ Spied for Months on AP Reporters  ewmayer  Soap Box  11  20130606 06:15 
disk died, prime work lost forever? where to put prime? on SSD or HDD?  emily  PrimeNet  3  20130301 05:49 
Breaking up files  roger  Information & Answers  13  20071117 06:50 
Beowolf cluster on the Cheap, breaking 100$/GFlop  jflin  Hardware  8  20070906 08:25 