Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question

3 Answers 3

up vote 4 down vote accepted

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.

share|improve this answer

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.

share|improve this answer
    
the multiplicative inverse of a prime number? 1/p ;) –  Vicfred Aug 15 '11 at 3:22
2  
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 –  user476 Aug 15 '11 at 3:39
    
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. –  Vicfred Aug 15 '11 at 3:41
1  
I believe that you are right. Not certain about this, as it has been a while since I last did it. Good luck! –  user476 Aug 15 '11 at 3:43
    
@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. –  user476 Aug 15 '11 at 3:57

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.)

share|improve this answer
    
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} –  PulpSpy Aug 15 '11 at 20:16
2  
for a "free and apparently very good" computer algebra system, check out Sage. –  TJ Ellis Aug 17 '11 at 23:46

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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