Elementary math question: primality test for huge numbers
Hi. I was working through a math chapter explaining the RSA algorithm, and I was implementing it in Haskell for learning sake. However, the chapter does not explain how you efficiently pick the two prime numbers. I scanned through the WP page on primality tests but it was somewhat overwhelming. What would be the standard primality test for this sort of application, and is it already built in to Base somewhere? -- Biblical creationism: http://tinyurl.com/qfyeg4a Free Bible software: http://xiphos.org Software freedom: http://tinyurl.com/qjnpnsm Free computer operating system: http://tinyurl.com/7wczchu Alternative to MS Office: http://tinyurl.com/aw9p6d4
See section 4.4. http://cacr.uwaterloo.ca/hac/about/chap4.pdf --Will Yager On Mon, Aug 24, 2015 at 12:34 AM, Christopher Howard <ch.howard@zoho.com> wrote:
Hi. I was working through a math chapter explaining the RSA algorithm, and I was implementing it in Haskell for learning sake. However, the chapter does not explain how you efficiently pick the two prime numbers. I scanned through the WP page on primality tests but it was somewhat overwhelming. What would be the standard primality test for this sort of application, and is it already built in to Base somewhere?
-- Biblical creationism: http://tinyurl.com/qfyeg4a Free Bible software: http://xiphos.org Software freedom: http://tinyurl.com/qjnpnsm Free computer operating system: http://tinyurl.com/7wczchu Alternative to MS Office: http://tinyurl.com/aw9p6d4
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Haskell also includes the primality testing functions of the GMP library on Integers, but they're MagicHashed for some reason so handle with care: https://hackage.haskell.org/package/integer-gmp-1.0.0.0/docs/GHC-Integer-GMP... On Mon, Aug 24, 2015 at 6:38 AM, William Yager <will.yager@gmail.com> wrote:
See section 4.4. http://cacr.uwaterloo.ca/hac/about/chap4.pdf
--Will Yager
On Mon, Aug 24, 2015 at 12:34 AM, Christopher Howard <ch.howard@zoho.com> wrote:
Hi. I was working through a math chapter explaining the RSA algorithm, and I was implementing it in Haskell for learning sake. However, the chapter does not explain how you efficiently pick the two prime numbers. I scanned through the WP page on primality tests but it was somewhat overwhelming. What would be the standard primality test for this sort of application, and is it already built in to Base somewhere?
-- Biblical creationism: http://tinyurl.com/qfyeg4a Free Bible software: http://xiphos.org Software freedom: http://tinyurl.com/qjnpnsm Free computer operating system: http://tinyurl.com/7wczchu Alternative to MS Office: http://tinyurl.com/aw9p6d4
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
If you don't mind using an external package, you can take a look Math.NumberTheory.Primes and related modules in the arithmoi[1] package. I've used it successfully for some small tasks, so I haven't come close to stress-testing it, but the interface was fine. [1]: http://hackage.haskell.org/package/arithmoi On Mon, Aug 24, 2015 at 3:52 AM, Patrick Chilton <chpatrick@gmail.com> wrote:
Haskell also includes the primality testing functions of the GMP library on Integers, but they're MagicHashed for some reason so handle with care:
https://hackage.haskell.org/package/integer-gmp-1.0.0.0/docs/GHC-Integer-GMP...
On Mon, Aug 24, 2015 at 6:38 AM, William Yager <will.yager@gmail.com> wrote:
See section 4.4. http://cacr.uwaterloo.ca/hac/about/chap4.pdf
--Will Yager
On Mon, Aug 24, 2015 at 12:34 AM, Christopher Howard <ch.howard@zoho.com> wrote:
Hi. I was working through a math chapter explaining the RSA algorithm, and I was implementing it in Haskell for learning sake. However, the chapter does not explain how you efficiently pick the two prime numbers. I scanned through the WP page on primality tests but it was somewhat overwhelming. What would be the standard primality test for this sort of application, and is it already built in to Base somewhere?
-- Biblical creationism: http://tinyurl.com/qfyeg4a Free Bible software: http://xiphos.org Software freedom: http://tinyurl.com/qjnpnsm Free computer operating system: http://tinyurl.com/7wczchu Alternative to MS Office: http://tinyurl.com/aw9p6d4
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
On Mon, Aug 24, 2015 at 1:38 AM, William Yager <will.yager@gmail.com> wrote:
See section 4.4. http://cacr.uwaterloo.ca/hac/about/chap4.pdf
If it helps to have a (small) prime number generator, there's an efficient implementation in exact-combinatorics[1] [1] <http://hackage.haskell.org/package/exact-combinatorics> -- Live well, ~wren
participants (5)
-
Christopher Howard -
Patrick Chilton -
Tikhon Jelvis -
William Yager -
wren romano