William,
You need a mathematician not a computer programmer.
This is classic number theory which must have been very well
explored. I have a very vague recollection that there may be
partial proofs that there are no primes between x and y or no
more than n primes between w and z for low ranges of numbers.
My instinct would be that you cannot, in general, know you are near
a prime. But that's based on a wishy-washy assumption that primes are
the only significant rational numbers and that all other rationals
are just short hand for prime relationships. Or rather, only the
primes and irrationals are necessary. Or, if you want a database
metaphor, only primes are 5th normal form.
Hope you are/are not trying to crack ciphers!
George
William Bailey wrote:
> Hello again.
>
> I have the following function that generates a prime number of x
> bits. It seems to work but i am just trying to see if i can make it any
> faster as generateing 1024 bit prime can take a while. so i thoought i
> would ask here to see if anybody has any ideas or suggestions.
>
> The function is as follows:
>
> mt_srand((double)microtime()*10000);
>
> function generate_prime ($bits) {
> $number=gmp_init('0');
> for($i=$bits; $i>=0; $i--){
> $rand=mt_rand()%2;
> gmp_setbit($number, $i, $rand);
> }
> while(gmp_prob_prime($number)<1){
> $number=gmp_add($number, 1);
> }
> if(strlen(gmp_strval($number, 2))!=$bits){
> $number=generate_prime($bits);
> }else{
> return (string)gmp_strval($number);
> }
> }
>
> At the moment im generating a random number of the required length and
> then +1ing it untill it is a prime. I suppose i really want to know if
> their is some way of knowing how close you are to a possiable prime so
> that if the random number is too far away then it could call itself again
> and try a different random start location.
>
> I look forward to any ideas that you might have.
>
> Regards,
> William.
>
> --
> William Bailey.
> http://wb.pro-net.co.uk
--
PHP General Mailing List (http://www.php.net/)
To unsubscribe, visit: http://www.php.net/unsub.php
