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.

Given a list of 2048 bit integer values in which one or few 2048 bit integer values may be product of two prime numbers and other values may be just 2048 bit odd integers numbers.

My question is - Is there a way / technique (apart from brute-force) to confirm that a given 2048 bit integer value is product of two prime numbers or not?

Is there any pattern in an integer value which is not product of two prime numbers?

share|improve this question
    
Could you define what you mean by "pattern in an integer value"? It's unclear to me if you're asking about specific bit-patterns, or simply about integer value characteristics… –  e-sushi Feb 1 at 19:42
    
@e-sushi: any pattern like bit pattern or integer value characteristics which indicate a given value is or not a product of two prime numbers. –  User2014 Feb 2 at 7:03
    
Well, if the last bit is 0, then it has a factor of 2 –  Cole Johnson Feb 7 at 19:45
    
Similar: crypto.stackexchange.com/q/1611/187 –  yydl Feb 9 at 4:40
add comment

5 Answers

No, there is no known test that we can run on a 2048 bit composite number that would indicate whether it was the product of two primes, or whether it was the product of more than two primes.

About the closest we can get is a zero knowledge proof; we know how someone (who does know the factorization) can run an interactive proof with us that can demonstrate to us that there are only two prime factors (and not reveal anything else). However, that does not appear what you're asking for.

share|improve this answer
    
you mean to say that no known test (apart from brute-force) for small or large integer values? –  User2014 Feb 2 at 11:42
1  
@User2014: there is no known test that is easier that factorization; for small (say, 128 bit) numbers, yes, we can determine whether the integer was a factor of two primes, but we can also factor that integer as well. Note that the 'answers' that Messer and Sebastian gave were really factorization methods. –  poncho Feb 2 at 12:32
2  
Can you add a bit of information about that ZKP? –  CodesInChaos Feb 3 at 8:39
    
I don't think there is a proof for exactly 2 distinct prime factors. You can proof that you know a nontrivial prime factor, or that you know the entire factorization. But I think you can not proof that there are exactly 2 of them. –  tylo Feb 3 at 15:20
    
@tylo See ftp.daimi.au.dk/BRICS/RS/98/29/BRICS-RS-98-29.pdf for a technique that allows this, as well as allowing you to show that the two primes are safe primes (should that be required). –  poncho Feb 3 at 15:43
show 1 more comment

If you have a quantum computer at hand then you can use
Shor's algorithm to find the prime factors in polynomial time.

share|improve this answer
    
This isn't exactly what the OP was asking. It sounds like the OP wants to know if a number is composite without having to find the factors. –  Cole Johnson Feb 8 at 19:43
1  
@ColeJohnson: actually the OP does not want to distinguish between prime numbers and composites (that one is easy); he wants to distinguish between composites which are the product of exactly two primes, and composites which are products of three primes or more (and for that one, we don't know of any method which is faster than actually factoring the integer, at least partially). –  Thomas Pornin Feb 8 at 20:42
add comment

There are priminality tests that can be executed very efficiently. They come in different flavors (AKS->for sure, Rabin-Miller->with a 1-1/2^k probability etc). They will tell you if a big number is prime or not (answer true/false), so they will not tell you whether the number is divided by two or more primes. If the question is only for two primes, then the answer is definitely not. There is no efficient algorithm (non-quantum) that can tell you by how many primes a given integer is divided.

share|improve this answer
    
Probabilistic Rabin-Miller is $1-1/4^k$ btw –  Thomas Apr 4 at 2:31
add comment

It is not possible to ensure a number is power of two primes (without effectively factoring the number). NIST has defined tests which are used in context of validating RSA public key, which you could use.


NIST recommends following tests (from NIST SP 800-89, section 5.3.3) for testing RSA public keys (which are supposedly product of two prime numbers):

  1. The length of the modulus is one of the specified values in FIPS 186-3.
  2. The value of the public exponent is in the valid range, as specified in FIPS 186-3.
  3. The modulus and the public exponent are odd numbers.
  4. The modulus is composite, but not a power of a prime
  5. The modulus has no factors smaller than 752. Testing for additional factors is allowed.

The tests 1-2 are specific to NIST specifications for RSA, however, tests 3-5 are generally useful. In your case also test 1 applies: 2048-bit was the size the question was about. Apply the tests for modulus to your large 2048-bit number. After these tests, it is (probably) proven that the number:

  • has no small factors (test 5)
  • the number is not a prime or a power of prime (test 4)

Test 4 is usually implemented using tests from FIPS 186-3 (enhanced Miller-Rabin test).

Note: in case the test 5 fails, it is still possible that the number is indeed product of two primes. (I.e. one of factors is a small prime and another is a large prime.) Such numbers are valid for "product of two primes", but are not useful in some cryptographic algorithms such as RSA.

All these tests will not prove that the value is product of two primes. Instead, a product of more primes may still pass the tests. A prime number, however, will be very unlikely to pass above tests.

These tests are convenient to implement in the sense that if you have cryptographic module which is capable of generating key for RSA, many of the tests are likely already implemented by it.


BTW, in case this is about RSA, you could be able to use some other means of public key validity checking, including e.g. TTP Key Pair Validation.

share|improve this answer
    
According to one of poncho's comments to this answer, this algorithm would $\hspace{1.94 in}$ be a good way to implement the last part of 5. $\:$ –  Ricky Demer Feb 3 at 18:09
    
@Ricky Demer: For testing factor up-to 752, it is possible to use $GCD(n, 14518877557776399015115874320830702024226143809848893135505709196593151770659565‌​743590789126541491676439926842369913057775743308316665115891457010597107422766927‌​578829157562209019982129757565432235504904310130610821310408080105652937489269014‌​42915057819663730454818359472391642885328171302299245556663073719855) = 1$, which is actually quite fast test to perform. But, beyond a predefined set of small primes, it is unsure if it is useful to continue further (unless you're actually trying to factorize). –  user4982 Feb 3 at 18:59
add comment
  • Calculate square root of your allegedly combined number (cn)
  • lookup prime number (pn) that is closest to it
  • lookup precomputed primorial (pp) for that prime number (pn)
  • calculate greatest common divisor of (pp) and (cn)
  • If the result is 1, the number (cn) is not combined and a prime number itself

Question is only where to get primorials for such high numbers, maybe ask the NSA ;)

share|improve this answer
4  
Actually, another question would be how you intend to compute the gcd between two numbers, when one of them is over $2^{1400}$ bits long... –  poncho Feb 2 at 3:21
add comment

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.