4
$\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?

Improve this question
$\endgroup$

3 Answers 3

Reset to default
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.

Improve this answer
$\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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ the multiplicative inverse of a prime number? 1/p ;) $\endgroup$
    – Vicfred
    Commented Aug 15, 2011 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
    Commented Aug 15, 2011 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
    Commented Aug 15, 2011 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
    Commented Aug 15, 2011 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
    Commented Aug 15, 2011 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.)

Improve this answer
$\endgroup$
2
  • $\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
    Commented Aug 15, 2011 at 20:16
  • 2
    $\begingroup$ for a "free and apparently very good" computer algebra system, check out Sage. $\endgroup$
    – Tara
    Commented Aug 17, 2011 at 23:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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