mersenneforum.org Factored my first SemiPrime -Some Questions
 Register FAQ Search Today's Posts Mark Forums Read

2011-05-16, 17:36   #23
jyb

Aug 2005
Seattle, WA

34668 Posts

Quote:
 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.

2011-05-16, 17:59   #24
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

22·1,877 Posts

Quote:
 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)

2011-05-16, 18:12   #25
jyb

Aug 2005
Seattle, WA

2·13·71 Posts

Quote:
 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.

2011-05-17, 22:18   #26
lavalamp

Oct 2007
Manchester, UK

1,373 Posts

Quote:
 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.

 2011-05-17, 23:21 #27 Christenson     Dec 2010 Monticello 5·359 Posts "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. Last fiddled with by Christenson on 2011-05-17 at 23:23 Reason: Read more, need to say thanks!
2011-05-17, 23:37   #28
CRGreathouse

Aug 2006

176316 Posts

Quote:
 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.

2011-05-18, 18:18   #29
jyb

Aug 2005
Seattle, WA

2×13×71 Posts

Quote:
 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?

2011-05-19, 01:56   #30
Christenson

Dec 2010
Monticello

179510 Posts

Quote:
 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.

 2011-05-22, 18:00 #31 lavalamp     Oct 2007 Manchester, UK 1,373 Posts 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.
2011-05-22, 18:17   #32
chris2be8

Sep 2009

2×1,213 Posts

Quote:
 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

 Similar Threads Thread Thread Starter Forum Replies Last Post sweety439 sweety439 11 2020-09-23 01:42 danaj Programming 17 2017-09-15 16:41 aketilander Factoring 4 2012-08-08 18:09 JHansen Factoring 47 2005-06-29 17:59 xilman Factoring 23 2005-06-02 03:24

All times are UTC. The time now is 10:05.

Sun Feb 5 10:05:32 UTC 2023 up 171 days, 7:34, 1 user, load averages: 0.86, 0.78, 0.71