Re: RSA algorithm

From: lakis (lakis2000_at_hotmail.com)
Date: 07/06/03 

Date: 6 Jul 2003 09:57:33 -0700

Michael Amling <nospam@nospam.com> wrote in message news:<3F083405.1050900@nospam.com>...
> vicky wrote:
> > Any idea?
> >
> > Suppose that the public key of RSA is (n,e) and C=M^e (mod n). An
> > algorithm A can invert 1% of the inputs in form y=M^e (mod n). Prove
> > that using algorithm A we can invert every input with high
> > probability.
> > Thank you :)
>
> Are you doing lakis's homework?
>
> --Mike Amling

I saw this exercise in the introduction to algorithms (about rsa) and
i couldn't find any solution. Since i'm practicing in these things,
trying to solve a series of exercises, some help could be useful. I
don't ask for the exact solution but an idea to work on...
Besides we have finished lessons and it's summer! :)

Relevant Pages

  • Re: Algorithm For Ensuring p & q Sufficiently Large For n in RSA
    ... probability of mathematical failure just means that you are getting your ... contract for an algorithm, then it should do that, ... adverse effect is less than chance of all of you spontaneously ...
    (sci.crypt)
  • Re: Primes algorithm
    ... > method which is generally used, as far as I know, is the Miller-Rabin ... > algorithm, ... > that a given number is composite, then it is definitely composite; ... A number is prime with a probability equal to either 0 or to 1. ...
    (sci.crypt)
  • Re: Deterministic Algorithm for Random Number Generation Using Coin Flips
    ... -the algorithm can guarantee that there is 0 probability that the ... algorithm will run forever. ... generator that is guaranteed to terminate after finite throws? ... the rng be random? ...
    (sci.math)
  • Re: Deterministic Algorithm for Random Number Generation Using Coin Flips
    ... -the algorithm can guarantee that there is 0 probability that the ... algorithm will run forever. ... (or assuming the coins were not labeled: toss #1, toss #2, or toss ... Take a red coin and a green coin and toss ...
    (sci.math)
  • Re: random variable
    ... Looking at the documentation for rand, I see that both the 'twister' ... and 'state' random number generators generate numbers in the closed ... implication is that there is an algorithm similar to r = 2^53 * n where n ... probability of producing any of the numbers in one of these intervals must ...
    (comp.soft-sys.matlab)