If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

## Computer science theory

### Course: Computer science theory>Unit 2

Lesson 7: Randomized algorithms

# Randomized algorithms (intro)

How could random numbers speed up a decision algorithm? Created by Brit Cruise.

## Want to join the conversation?

• As n grows, primes become less and less common. Eventually, could you reach a point that there are no more primes? • At , we just need to be 99.9999999999999% sure that it's a prime. So, if we have an error and actually get that 1.0e-15 chance that it's not a prime number, going back to RSA, how does this unprime number weaken the encryption? would it mess up the encrypted message itself? how to exploit this leak? • If p or q is not prime it breaks the RSA algorithm, since it is based on p and q being prime, so that we can choose e and d properly to encrypt and decrypt messages.

What will happen is:
-you will encrypt some plain text M using the public key e to get a cipher text C
-the person will decrypt C using the private key d to get a plain text M'
-M and M' probably won't be the same

Why does this happen?

RSA relies on properties of Fermat's little theorem,or Eulers theorem, both of which assumes p and q are prime.

M mod n= C^e mod n
C mod n= M^d mod n

M mod n= (M'^d mod n)^e mod n = (M'^d)^e mod n = M'^(e * d) mod n

If p,q are prime, Fermat's Little Theorem (or Euler's Theorem) can be used to show us that M'^ (e * d) mod n = M' mod n.
(I've excluded the gory math details, but they also rely on how we chose e and d)
If p and q are not both prime, the value M'^ (e * d) mod n will likely not be M' mod n.

Let's suppose, for a moment, that RSA still worked even though we chose p as a composite.
Having p as a composite would mean we had, at least, two factors >1 for p.
This means we have, at least, 3 factors for n now.
If we had only two factors the largest that the smallest factor could be is the square root of n.
Now, with 3 factors, the largest that the smallest factor could be is the cubed root of n, which is much smaller.
This would make a brute force attack to factor n much easier. (factoring n can be used to reveal the private key)

Hope this makes sense
• Are there "primes and composites" in negative numbers? • There is this theorem called Fermat's theorem, which tests for primes.

Fermat's theorem states that if p is prime and 1 is less than or equal to a which is less than p, then
a^p-1 (mod sign) 1 (mod p)
If we want to test if p is prime, then we can pick random a's in the interval and see if the equality holds. If the equality does not hold for a value of a, then p is composite. If the equality does hold for many values of a, then we can say that p is probable prime.
It might be in our tests that we do not pick any value for a such that the equality fails. Any a such that
a^n-1 (mod sign) 1 (mod n)

when n is composite is known as a Fermat liar. Vice versa, in this case n is called Fermat pseudoprime to base a.
If we do pick an a such that
a^n-1 (mod sign with a slash through it) 1 (mod n)
then a is known as a Fermat witness for the compositeness of n.

Thanks to Wikipedia! • can we see visual lecture on any other site? here at pakistan youtube is ban from government • How are random numbers actually generated? • What is the chance that I win the lottery twice in a row? Isn't it less likely that I win it twice in a raw than just twice at any two of the weekly draws? And isn't it less likely than just winning the first one and a 1:2 chance of winning the second one? I think the calculation is wrong in the beginning on the video, but I am not sure. • It's the same as rolling a dice twice in a row. Let's say winning lottery = rolling a 6. Rolling two sixes at the same time, or one six followed by another six is the same: 1/6*1/6 = 1/36.
It doesn't really matter how much time is in-between draws (or rolls)

However, if you are asking about the probability of winning twice over many draws (say inside of a year), then yes that is a different question (and more likely)
• that machine said that if a number isn't expressible in the form 6k+/-1, it's 100% proof that the number is a composite but 2 and 3 can't be expressed in that form and they're primes. So is this little test still proof of composites? • How does odds of hitting lottery twice in the row is 6 * 10^-14, can anybody explain me?
(1 vote) • Probability of winning the 6/49 lottery once is:
1/(49 C 6)
where:
49 C 6 is the number of ways we can choose 6 items from 49 (order doesn't matter).
49 C 6 = 49!/(43! * 6!) = 13,983,816
So, the odds of winning once is : 1/13,983,816

Winning the lotto twice (assuming the events are independent) is :
1/13,983,816 * 1/13,983,816 = 1/195,547,109,921,856 ~= 5 * 10^-15

So, 6 * 10^-14 appears to be off a little.
• I got lost at the 6k +/- 1. No idea where that came from • Prime numbers are in the form 6k+1 or 6k-1 where k is some integer. (But not all numbers in this form are necessarily prime).

Why ?
All integers, are in one of these forms:
6k, 6k+1, 6k+2, 6k+3, 6k+4, 6k+5
(This is a result of the quotient remainder theorem that states: Given any integer A, and a positive integer B, there exist unique integers Q and R such that A = B * Q + R where 0 ≤ R < B )
Numbers of the form:
6k are divisible by 6 thus not prime
6k + 2 = 2 * (3k+1) so divisible by 2 thus not prime
6k + 3 = 3 * (2k+1) so divisible by 3 thus not prime
6k + 4 = 2 * (3k+2) so divisible by 2 thus not prime
Which leave us with:
6k+1, 6k+5 being potentially prime
6k-1 is equivalent to 6k+5 because we can use the next higher k as follows: 6(k-1)+5= 6k-1
e.g. 17 = 6 * 2 + 5 = 6 * 3 - 1
(Or we could just say because -1 mod 6 = 5)
So we can just use 6k +/- 1

Hope this makes sense