mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Msieve

Reply
 
Thread Tools
Old 2011-05-16, 17:36   #23
jyb
 
jyb's Avatar
 
Aug 2005
Seattle, WA

34668 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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.
jyb is offline   Reply With Quote
Old 2011-05-16, 17:59   #24
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

22·1,877 Posts
Default

Quote:
Originally Posted by jyb View Post
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)
R.D. Silverman is offline   Reply With Quote
Old 2011-05-16, 18:12   #25
jyb
 
jyb's Avatar
 
Aug 2005
Seattle, WA

2·13·71 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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.
jyb is offline   Reply With Quote
Old 2011-05-17, 22:18   #26
lavalamp
 
lavalamp's Avatar
 
Oct 2007
Manchester, UK

1,373 Posts
Default

Quote:
Originally Posted by Christenson View Post
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.
lavalamp is offline   Reply With Quote
Old 2011-05-17, 23:21   #27
Christenson
 
Christenson's Avatar
 
Dec 2010
Monticello

5·359 Posts
Default

"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!
Christenson is offline   Reply With Quote
Old 2011-05-17, 23:37   #28
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

176316 Posts
Default

Quote:
Originally Posted by lavalamp View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2011-05-18, 18:18   #29
jyb
 
jyb's Avatar
 
Aug 2005
Seattle, WA

2×13×71 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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?
jyb is offline   Reply With Quote
Old 2011-05-19, 01:56   #30
Christenson
 
Christenson's Avatar
 
Dec 2010
Monticello

179510 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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.
Christenson is offline   Reply With Quote
Old 2011-05-22, 18:00   #31
lavalamp
 
lavalamp's Avatar
 
Oct 2007
Manchester, UK

1,373 Posts
Default

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.
lavalamp is offline   Reply With Quote
Old 2011-05-22, 18:17   #32
chris2be8
 
chris2be8's Avatar
 
Sep 2009

2×1,213 Posts
Default

Quote:
Originally Posted by lavalamp View Post
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
chris2be8 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Semiprime and n-almost prime candidate for the k's with algebra for the Sierpinski/Riesel problem sweety439 sweety439 11 2020-09-23 01:42
Generating a uniform random n-bit semiprime danaj Programming 17 2017-09-15 16:41
Factored vs. Completely factored aketilander Factoring 4 2012-08-08 18:09
2,709+ factored JHansen Factoring 47 2005-06-29 17:59
RSA-200 factored 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2023, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔