- **Math**
(*https://www.mersenneforum.org/forumdisplay.php?f=8*)

- - **Breaking a prime p into a^2 + 3* b^2**
(*https://www.mersenneforum.org/showthread.php?t=12346*)

Breaking a prime p into a^2 + 3* b^2I'm playing with [URL="http://en.wikipedia.org/wiki/Cubic_reciprocity"]cubic reciprocity[/URL] formulas.
From that link, it states "A theorem of Fermat states that every prime [I]p[/I] ≡ 1 (mod 3) is the sum of a square and three times a square: [B][I]p[/I] = [I]a^[/I]2 + 3[I]b^[/I]2[/B]" 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 [URL="http://en.wikipedia.org/wiki/Quartic_reciprocity"]quartic reciprocity? [/URL] |

[QUOTE=SPWorley;187339]I'm playing with [URL="http://en.wikipedia.org/wiki/Cubic_reciprocity"]cubic reciprocity[/URL] formulas.
From that link, it states "A theorem of Fermat states that every prime [I]p[/I] ≡ 1 (mod 3) is the sum of a square and three times a square: [B][I]p[/I] = [I]a^[/I]2 + 3[I]b^[/I]2[/B]" How would you go about finding a and b given p? ][/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. |

[quote=SPWorley;187339]How about the case where p=a^2 +2* b^2, which comes up when dealing with [URL="http://en.wikipedia.org/wiki/Quartic_reciprocity"]quartic reciprocity? [/URL][/quote]
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. |

Thanks very much for the references.. it's all there in Crandall/Pomerance.
Pretty straightforward, too! I appreciate it. |

All times are UTC. The time now is 11:45. |

Powered by vBulletin® Version 3.8.11

Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.