PDA

View Full Version : prime number properties

dion
April 18th, 2002, 08:27
i'm interested in rsa algo which is heavily based on prime number. i don't remember when, that long ago in my school, i'm teached about calculating list of prime with aritmetic only. of course that is small number. but i'm forget that thing. do anyone know that? what i mean from this is...
is it possible to find next prime if i know the prime number N in large order, without having to test it's primality ?

Kythen
April 18th, 2002, 15:47
Nope, so far no one has been able to find a solid pattern by which you can pick/find prime numbers. Hence the contests to find the largets prime number. You can calculate the primes less than a given number N by using an algorithm called the Sieve of Eratosthanes. Of course, that's rather impractical for numbers of the size which are used in RSA.

mike
April 18th, 2002, 16:02
Ther are also probabalistic primality checks, i.e. after passing k checks there's a 2^(-k) probability that the number isn't prime.

dion
April 19th, 2002, 09:50
i don't know what is called. but it looks like :
(a+b), (c+d), ...
and these numbers is primes. i think with addition only could faster rsa process. and, i'm got another idea. have anyone heard about calculator man ? how he can do that ? is it can be applied to faster rsa process ?

Kythen
April 19th, 2002, 16:20
Ummm.... *all* numbers can be written in the form (a + b). Some primes may be of a specific form, like the Mersienne primes that are 1 less than a power of 2. I don't believe extra additions will be of much help with RSA. There are already good algorithms for fast exponentiation.

I haven't heard of calculator man, but I'm guessing it's some guy that can do basic arithmetic with large numbers in his head. All he does is use a different algorithm for the various arithmetic operators from the one everyone learns in elementary school. It's basically the same, except that you work from the most significant digit on down. Take 123 + 456 for example. First tak 100 + 400 = 500. Then 20 + 50 = 70 -> 70 + 500 = 570. Last 3 + 6 = 9 -> 570 + 9 =579. It works pretty well when you don't have nice round numbers to work with. I don't believe this would help if it's not already being done in bignum libraries, though Mike feel free to correct me on any of this

dion
April 20th, 2002, 03:54
Helo Kythen & Mike
may be i must search more about this calculator man. and accidentally, still related to calculator, my genious friend ask me a little interesting question. anyone must be know about fraction. well, i almost forgot that now, i remember that when i reading elementary number theory.
might be it looks like this:

A = B / (1 + 1/C)

he ask me to show some a real number (i mean when u use calculator, u type A/B and enter and that's what i mean with, and he warn me to choose A and B so that both are odd.

and i do that, and give him the result without he know what the A and B are. what he do is he trying to find A and B with fraction method (i know that after reading the book).

after that, he ask me like this :
given any large number, say bignum type, is it can
be represented with A/B with this method ?
if can, prove it, if not, prove it too!

i can't answer that until now. and after i know little about crypto, i wonder if it can, it might be can reduce or faster bignum process.

Kythen
April 20th, 2002, 07:56
Ahhh... what you have there are things called continued fractions. Yes they can be used to represent any real number. Finite continued fractions represent rational numbers. Infinite continued fractions converge to irrational numbers. If an infinite continued fraction is periodic, like say [2 1 2 1 2 1 ...] then it is the root of a quadratic polynomal Ax^2 + Bx + C.
You can do the basic arithmetic operations on them as well. However, the algorithms you use when working with numbers in this representation are actually matrix operations. Because of this, they work out to be a fair amount slower than arithmetic in our normal decimal/binary representation. You can get much more accurate results with continued fractions though.
They are useful in crypto to a certain extent. There is a factoring algorithm that uses continued fractions, but it is limited to numbers of about 50 digits max.

Hope that clears things up a bit!

mike
April 20th, 2002, 18:49
Continued fractions actually mimic the GCD algorithm. In GCD, you take two numbers, one modulo the other. GCD throws away the number of multiples and only keeps the remainder; those multiples are the terms in the continued fraction.

For example, GCD(6,9) is calculated like this:
Code:
```
6 = 6 + 9*0
swap 6,9
9 = 3 + 6*1
swap 3,6
6 = 0 + 3*2
^   ^ GCD
```

So GCD(6,9)=3

We can take the last column and get the continued fraction
[ 0 1 2 ] = 0 + 1/( 1 + 1/2) = 0 + 1/ (3/2) = 2/3 = 6/9

That should give you a hint as to why a terminating CF is rational. If you can't figure it out, check out the mathworld page on CF's.

dion
April 22nd, 2002, 03:28
yep! u both right!
looks like i've lot of wrong things here. about the fraction, after revisited it again, i found that thing referenced in Knuth(81). it's named finite continued fraction. that's exactly what i want to ask. but after do some calc, i found prime is not practical to be represented in fraction form . and that's all what i wanna do. wondering if it practical...

but, i'm still seeking how to speed rsa process more. yep! i see something in CryptoBytes January 2002 from RSA. there's a proposed 3 formulas. among them which interested me is named Multi-Factor RSA with form N = pqr or N = (p^2)q. i remember there's one who ask how it can be if N = pqr in this forum. but no answer regarding to this. may be the topic at the time is different. and to repeat it, could anyone tell me how this form can be implemented ? it's not i'm lazy to read that, but just can't understand it. could it be explained in rather simple so me newb can eat it ?

oh, about calculator man. after searching, i found it named mental arithmatica. do u guys know more about it ? it somehow related to abacus.

mike
April 22nd, 2002, 14:13
Works the same way as RSA but n=pqr, phi(n)=(p-1)(q-1)(r-1), d=e^-1 mod phi(n).

dion
April 23rd, 2002, 09:54
ho yeah...
seems simple, thanks Mike and Kythen. this thread is somehow roaming and i'm feel really very stupid here. but, anyway thanks guys, i think i'd learn more and more like ur ban Kythen.
Cya