3
$\begingroup$

When implementing cryptographic/coding theory algorithms one need to use data like big prime numbers, numbers in $Z_n$ and their inverses, irreducible polynomials in $Z_n[x]$ and so on...

While sometimes it is easy to write a simple program to get simple examples of these it's handy to have a list with some non-trivial examples. Do you know where can I find such data?

$\endgroup$
4
$\begingroup$

Generating prime integers and computing things modulo integers is easy with a programming language which features support for big integers. I usually use Java: it includes java.math.BigInteger, with which one can:

  • generate prime integers of any length;
  • do all basic operations, including modular reduction (mod() method);
  • compute modular inverses (modInverse());
  • compute modular exponentiations (modPow()).

For irreducible polynomials, things are more complex: Java does not offer a generic method for testing irreducibility of polynomials (or, for that matter, anything related to polynomials). I do have my own library but it is not generally available (I implemented it for a customer). However, my friend Google points out that this library appears to be fairly complete in that area.

$\endgroup$
2
$\begingroup$

As far as very large prime numbers, have a look at the following link.

http://primes.utm.edu/largest.html

It gives you a summary of the largest known primes. Good luck with calculating their multiplicative inverses, though. That will not be so easy.

$\endgroup$
  • $\begingroup$ the multiplicative inverse of a prime number? 1/p ;) $\endgroup$ – Vicfred Aug 15 '11 at 3:22
  • 2
    $\begingroup$ No, the multiplicative inverses of numbers in the prime field $Z_p$ (i.e. $a$ modulo the prime number $p$). For that, you will need to use the Extended Euclidean Algorithm. Have a look at the following link to some lecture notes on how to do this. www.ijecbs.com/July2011/14.pdf $\endgroup$ – user476 Aug 15 '11 at 3:39
  • $\begingroup$ I know, I was just making it clear. Also, multiplicative inverses in Z_n can be computed faster using Euler's theorem and Fermat's little theorem. $\endgroup$ – Vicfred Aug 15 '11 at 3:41
  • 1
    $\begingroup$ I believe that you are right. Not certain about this, as it has been a while since I last did it. Good luck! $\endgroup$ – user476 Aug 15 '11 at 3:43
  • $\begingroup$ @Vicfred - Oops! Sorry, gave you the wrong link before. Here's a link to the quick view of the PDF that I was referring to earlier. docs.google.com/… If you do a google search, you should be able to find the PDF. $\endgroup$ – user476 Aug 15 '11 at 3:57
2
$\begingroup$

If you use a high-level mathematical language (Mathematica, Maple, etc.), generating this data is very easy. I use Mathematica personally, but some are free and apparently very good.

In a pinch, you can use Wolfram Alpha to do a lot:

Generate random prime:

RandomPrime[{2^1023,2^1024}]

Random integer:

RandomInteger[{2^1023,2^1024}]

Inverse mod p: (Returns random prime p, random integer a, a^-1 mod p)

{#,#2,PowerMod[#2,-1,#]}&@@Flatten[{#,RandomInteger[{1,#}]}&/@{RandomPrime[{2^1023,2^1024}]}]

It gets tricky supplying large numbers because queries are limited to 200 characters. Also you can't store variables and use them in subsequent queries. That is why using the actual applications is better. (For example, the last query above would simply be PowerMod[a,-1,p] if you could store a and p after you generate them.)

$\endgroup$
  • $\begingroup$ The fun part is getting Wolfram Alpha to generate a safe prime, short of running this query over and over again: {#,PrimeQ[#]}&/@{(RandomPrime[{2^1023,2^1024}]-1)/2} $\endgroup$ – PulpSpy Aug 15 '11 at 20:16
  • 2
    $\begingroup$ for a "free and apparently very good" computer algebra system, check out Sage. $\endgroup$ – TJ Ellis Aug 17 '11 at 23:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.