20110516, 17:36  #23  
Aug 2005
Seattle, WA
3466_{8} Posts 
Quote:
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 squarefree. 

20110516, 17:59  #24  
"Bob Silverman"
Nov 2003
North of Boston
2^{2}·1,877 Posts 
Quote:
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 noninteractive Statistical Zero Knowledge Proof System for Quasisafe Prime Products", Proc. 5th ACM Conf. on Computer and Communications Security These give ZKP's for semiprimes. (and also prove the primes are of nearly equal size) 

20110516, 18:12  #25  
Aug 2005
Seattle, WA
2·13·71 Posts 
Quote:


20110517, 22:18  #26  
Oct 2007
Manchester, UK
1,373 Posts 
Quote:
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. 

20110517, 23:21  #27 
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 20110517 at 23:23 Reason: Read more, need to say thanks! 
20110517, 23:37  #28  
Aug 2006
1763_{16} Posts 
Quote:


20110518, 18:18  #29  
Aug 2005
Seattle, WA
2×13×71 Posts 
Quote:
The remark at the end of section 3.2 says that the previous two sections can be combined to act as a onesided ZKP that the given composite is a semiprime. In particular, it claims that section 3.1 gives a 1ZKP that the composite is squarefree, 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 squarefree and that for any primes p,q dividing it, p does not divide q1. 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? 

20110519, 01:56  #30 
Dec 2010
Monticello
1795_{10} Posts 
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.

20110522, 18:00  #31 
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 multithreaded? It seems like the sort of thing that could be easily parallelised, but then I don't know all the ins and outs. 
20110522, 18:17  #32  
Sep 2009
2×1,213 Posts 
Quote:
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 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Semiprime and nalmost prime candidate for the k's with algebra for the Sierpinski/Riesel problem  sweety439  sweety439  11  20200923 01:42 
Generating a uniform random nbit semiprime  danaj  Programming  17  20170915 16:41 
Factored vs. Completely factored  aketilander  Factoring  4  20120808 18:09 
2,709+ factored  JHansen  Factoring  47  20050629 17:59 
RSA200 factored  xilman  Factoring  23  20050602 03:24 