Re: Security of RSA and factoring

Thread View: sci.crypt

1 messages

[T] Back to Threads [V] Tree View [G] Group Articles

1 total messages Started by Sam HLO2-1/G11 225-4135 Mon, 19 Jan 1987 14:43

#3337

Author: Sam HLO2-1/G11 225-4135
Date: Mon, 19 Jan 1987 14:43

21 lines
1466 bytes

Simson Garfinkel writes
>WAIT! It is not "easy" to test a 100-digit number for priamity.
> 
>How do you do that? To tell if a number is prime or not, you factor it.

Come on, Simson. Have you never heard of probablistic factorization?
Or read Michael Rabin's paper _Probablistic Algorithm for 
Testing Primality_ ? 

To be more precise, I would say "The only way to *prove* if a 
100-digit number is prime with 100% certainty is to factor it (or
*prove* no factors exist). We can *show* a number to be prime with
very high likelihood (as high as you have the computer resources
to test) by applying Rabin's algorithm."

[Aside from a former to MIT student to another: Mattuck showed Rabin's
algorithm in 18.063, and Shafi covered it in detail in 6.875, which
is a good graduate course in cryptography.]

Sam Levitin	Levitin%SEMI.DEC@decwrl		[MIT '85, '86]
DEC Hudson-LSI	77 Reed Road, Hudson MA 01749	(617) 568-4135

Thread Navigation

This is a paginated view of messages in the thread with full content displayed inline.

Messages are displayed in chronological order, with the original post highlighted in green.

Use pagination controls to navigate through all messages in large threads.

Back to All Threads