Factored my first SemiPrime -Some Questions

[jyb]

Originally Posted by R.D. Silverman

If *he* knows the factors then he can conduct a ZKP with you to convince
you. Otherwise, you are SOL.

Can you expand on that? There are of course some obvious ZKPs that would convince you that I know the factors of a particular large composite. But assuming you don't trust me when I then claim it's a semiprime, what ZKP can I use to convince you of that?

At first I was envisioning something along the lines of RSA; i.e. I make you encrypt a message using the composite as the modulus (with a suitable choice of e, of course), then show that I can decrypt it. But of course RSA doesn't require that the modulus be a semiprime, so it would only convince you that the composite is square-free.

[R.D. Silverman]

Originally Posted by jyb

Can you expand on that? There are of course some obvious ZKPs that would convince you that I know the factors of a particular large composite. But assuming you don't trust me when I then claim it's a semiprime, what ZKP can I use to convince you of that?

At first I was envisioning something along the lines of RSA; i.e. I make you encrypt a message using the composite as the modulus (with a suitable choice of e, of course), then show that I can decrypt it. But of course RSA doesn't require that the modulus be a semiprime, so it would only convince you that the composite is square-free.

See, e.g.

R.D. Silverman RSA Public Key validation
Proc. Workshop on Cryptography & Computational No. Theory
'CCNT 99 (Birkhauser, Progress in Computer Science & Applied Logic #20)

or:

Gennaro, Micciancio, Rabin, "An Efficient non-interactive Statistical
Zero Knowledge Proof System for Quasi-safe Prime Products", Proc. 5th ACM
Conf. on Computer and Communications Security


These give ZKP's for semi-primes. (and also prove the primes are of nearly
equal size)

[jyb]

Originally Posted by R.D. Silverman

See, e.g.

R.D. Silverman RSA Public Key validation
Proc. Workshop on Cryptography & Computational No. Theory
'CCNT 99 (Birkhauser, Progress in Computer Science & Applied Logic #20)

or:

Gennaro, Micciancio, Rabin, "An Efficient non-interactive Statistical
Zero Knowledge Proof System for Quasi-safe Prime Products", Proc. 5th ACM
Conf. on Computer and Communications Security


These give ZKP's for semi-primes. (and also prove the primes are of nearly
equal size)

Cool, thanks.

[lavalamp]

Originally Posted by Christenson

Student question, ignoring the obvious ethics issues raised by Jason:
Suppose I know nothing of Hian's number. How, besides feeding it to TF, or otherwise factoring it, would I show that it was indeed a semiprime? (I'm still working on MPQS as an introduction to NFS)

You could run ECM on it, not long enough to factor it, but long enough to be arbitrarily sure that it has no factors below the cuberoot of the number. In this case you could run quite a lot of curves with B1=3 million with a very small chance of finding a factor over 50 digits, but an overwhelming chance of finding any factor less than or equal to 40 digits.

This would require you to not accidentally factor the number in the process of course. So it could be used for semiprimes with similarly sized factors, or at least where both of the factors are above the cube root of the number.

[Christenson]

"Accidentally" factoring the number is an acceptable outcome...I was wondering how to put in less effort than a complete factoring job.

And thanks for the references on the ZKP, Mr Silverman.

[CRGreathouse]

Originally Posted by lavalamp

You could run ECM on it, not long enough to factor it, but long enough to be arbitrarily sure that it has no factors below the cuberoot of the number. In this case you could run quite a lot of curves with B1=3 million with a very small chance of finding a factor over 50 digits, but an overwhelming chance of finding any factor less than or equal to 40 digits.

I wonder what the crossover point would be such that being confident (say, 99%) that the number had no prime factors below its cube root by ECM would be no easier than simply factoring it with GNFS.

[jyb]

Originally Posted by R.D. Silverman

See, e.g.

R.D. Silverman RSA Public Key validation
Proc. Workshop on Cryptography & Computational No. Theory
'CCNT 99 (Birkhauser, Progress in Computer Science & Applied Logic #20)

or:

Gennaro, Micciancio, Rabin, "An Efficient non-interactive Statistical
Zero Knowledge Proof System for Quasi-safe Prime Products", Proc. 5th ACM
Conf. on Computer and Communications Security


These give ZKP's for semi-primes. (and also prove the primes are of nearly
equal size)

I haven't yet gotten ahold of your paper, but I do have a question about the Gennaro, Micciancio and Rabin paper, if you don't mind.

The remark at the end of section 3.2 says that the previous two sections can be combined to act as a one-sided ZKP that the given composite is a semiprime. In particular, it claims that section 3.1 gives a 1ZKP that the composite is square-free, and that section 3.2 gives a 1ZKP that the composite is a product of at most two distinct prime powers. Combining those gives the desired result.

However, it looks to me as if neither of sections 3.1 or 3.2 actually shows the claimed result. They actually show something slightly different. 3.1 gives a 1ZKP that the composite is square-free and that for any primes p,q dividing it, p does not divide q-1. And 3.2 gives a 1ZKP that the composite is a product of at most two distinct prime powers and that the two odd primes p and q are not congruent mod 8 and they are both not 1 mod 8.

Now if the purpose is to validate an RSA modulus, then one can choose a modulus with those extra conditions. But in general, if I have e.g. a semiprime with two factors p and q, and p = q (mod 8), then it doesn't appear as if the 1ZKP given in this paper will do the job of convincing someone that it really is a semiprime.

Does your paper give a ZKP that will work more generally?

[Christenson]

Originally Posted by CRGreathouse

I wonder what the crossover point would be such that being confident (say, 99%) that the number had no prime factors below its cube root by ECM would be no easier than simply factoring it with GNFS.

Shortest compute time, according to some measure, is also an acceptable outcome to me...that is, if it takes 2 days to GNFS, and 2 days to ECM, yes, might as well run GNFS and get the actual factors. But if that "lot of ECM" takes only an hour, or a minute, then the ECM gets pretty interesting.

[lavalamp]

I asked a friend with some spare CPU time to crack it open. On a 2.8 GHz quad core i7 w/ hyperthreading, msieve decided to take 5 hours 41 minutes to look for a polynomial (which seems much too long to me), and then the lattice sieving took 9 hours 7 minutes using 8 threads. Then a further 51 minutes were required to finish it up.

The number has two prime factors, 61 and 62 digits.

To anyone who may know about such things, how come the polynomial search isn't multi-threaded? It seems like the sort of thing that could be easily parallelised, but then I don't know all the ins and outs.

[chris2be8]

Originally Posted by lavalamp

To anyone who may know about such things, how come the polynomial search isn't multi-threaded? It seems like the sort of thing that could be easily parallelised, but then I don't know all the ins and outs.

f you use the script from http://mersenneforum.org/showthread.php?t=14425&page=3 it will use multiple threads for polynomial selection. Make sure you get the last of the three versions I posted (from post 64), it has more bugs fixed.

I'm working on a version to distribute polynomial selection over more that 1 computer. But I need a few free days for testing etc.

Chris K