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 ?

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.

Ther are also probabalistic primality checks, i.e. after passing k checks there's a 2^(-k) probability that the number isn't prime.

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 ?

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

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.

how about that guys ?

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!

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:

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.

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.

Works the same way as RSA but n=pqr, phi(n)=(p-1)(q-1)(r-1), d=e^-1 mod phi(n).

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