Hacker News Reader

Comment by Retric | Hacker News Reader

If you add three large primes I don't see how you could quickly reverse that process. May be possible that several set's of 3 primes also sum to that number so you would need a process for finding all of them.

View on HN

Factorisation is unique, the addition of 3 primes is not.

e.g. 29 can be written 5 + 11 + 13 or 3 + 3 + 23

So even if it were a difficult operation to reverse addition of 3 numbers, it would be made easier by collisions.

>Factorisation is unique //

Um, no it isn't.

6, 4 are factors of 24; 2, 12 are factors of 24.

Probably you meant prime decomposition.

I think he means that prime factorization is unique (which is true).

http://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmet...

Isn't that what I said?

I could have sworn that last sentence wasn't there (my bad).

Thinking about it more this is basically a special case of the knapsack problem. Which is not obviously impossible, and indeed was used in an early attempt at public-key cryptography, but has since been broken: http://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsack... .

It was cracked because it depended on a super-increasing sequence, the knapsack problem is still NP-Hard. However, finding a given sequence of primes that sum to the number is not really the knapsack problem.

If I recall correctly, the private key was super increasing. The knapsack encryption algorithm attempted to reduce the super-increasing sequence to a regular sequence. What was broken was that the reduced sequence, while no longer super-increasing, still turned out to be a special case which was easy to solve.

The known prime number - (3 + 5) ?

This is extremely amenable to a rainbow attack - just start here, http://primes.utm.edu/lists/small/1000.txt.

This is less amenable to a rainbow attack than cracking RSA. When cracking RSA you have to factorise a number N into P.Q, so you only have to check up to sqrt(N). With this, you have to get 3 numbers, and check up to N/3.

Reply on news.ycombinator.com