|
|
php.net | support | documentation | report a bug | advanced search | search howto | statistics | random bug | login |
[2011-08-27 09:09 UTC] sergio dot bobillier at gmail dot com
Description:
------------
I was doing a lame RSA implementation when I discovered that mt_rand only generates even numbers when the number is a 64 bits integer.
The Test script shows the script I used to generate two 64 bits integers p and q with mt_rand. I was doing primality test only with odd numbers since even numbers are not prime but the script never do the primality test because all the generated numbers are even.
I thought this might be an integer overflow problem but I'm doing this on a 64 bits system and the var_dump function shows that the variables are actually integers like so:
int(2117698586505379840)
int(1690740540401778688)
int(3279295862706012160)
int(4526730875131396096)
int(3188107862534520832)
int(1914802535743356928)
int(4172596828035874816)
int(4559249790717657088)
int(1938449129751445504)
int(1859647742213619712)
Test script:
---------------
function is_prime($num)
{
// See if the number is prime
echo "Primality test";
return true;
}
function gen_keys()
{
// 1. find two 64 bits primes p and q
$p = 0;
$q = 0;
while(!$p)
{
$p = mt_rand(72057594037927936, 4611686018427387904);
// debugging:
var_dump($p);
if($p % 2 == 0)
{
$p = 0;
}
else
{
// Primality test in another function
// (not important here)
echo "odd";
if(!is_prime($p))
$p = 0;
}
}
echo $p;
}
Expected result:
----------------
I expect the mt_rand to generate some odd numbers and make the script go through the primality test or at least print "odd"
Actual result:
--------------
The script doesn't reach the primality or print "odd" test because all generated numbers are even.
PatchesPull RequestsHistoryAllCommentsChangesGit/SVN commits
|
|||||||||||||||||||||||||||
Copyright © 2001-2024 The PHP GroupAll rights reserved. |
Last updated: Thu Sep 12 04:01:28 2024 UTC |
OK, so this behaves normally for bounds up to 2^32, then does weird things after that. Given this script: <?php $iterations = 1000; function mt_check($lower, $upper) { global $iterations; $stats = array_reduce(array_map(function ($v) use ($lower, $upper) { return mt_rand($lower, $upper); }, range(1, $iterations)), function ($acc, $v) { $v % 2 ? $acc['odd']++ : $acc['even']++; return $acc; }, array('odd' => 0, 'even' => 0)); echo "Stats for $iterations iterations of $lower..$upper: $stats[odd] odd; $stats[even] even\n"; } foreach (range(2, 62) as $pow) { mt_check(pow(2, $pow - 1), pow(2, $pow)); } ?> The results are this: Stats for 1000 iterations of 2..4: 319 odd; 681 even Stats for 1000 iterations of 4..8: 414 odd; 586 even Stats for 1000 iterations of 8..16: 452 odd; 548 even Stats for 1000 iterations of 16..32: 443 odd; 557 even Stats for 1000 iterations of 32..64: 475 odd; 525 even Stats for 1000 iterations of 64..128: 492 odd; 508 even Stats for 1000 iterations of 128..256: 486 odd; 514 even Stats for 1000 iterations of 256..512: 482 odd; 518 even Stats for 1000 iterations of 512..1024: 505 odd; 495 even Stats for 1000 iterations of 1024..2048: 502 odd; 498 even Stats for 1000 iterations of 2048..4096: 480 odd; 520 even Stats for 1000 iterations of 4096..8192: 485 odd; 515 even Stats for 1000 iterations of 8192..16384: 501 odd; 499 even Stats for 1000 iterations of 16384..32768: 513 odd; 487 even Stats for 1000 iterations of 32768..65536: 508 odd; 492 even Stats for 1000 iterations of 65536..131072: 498 odd; 502 even Stats for 1000 iterations of 131072..262144: 510 odd; 490 even Stats for 1000 iterations of 262144..524288: 514 odd; 486 even Stats for 1000 iterations of 524288..1048576: 498 odd; 502 even Stats for 1000 iterations of 1048576..2097152: 496 odd; 504 even Stats for 1000 iterations of 2097152..4194304: 488 odd; 512 even Stats for 1000 iterations of 4194304..8388608: 497 odd; 503 even Stats for 1000 iterations of 8388608..16777216: 493 odd; 507 even Stats for 1000 iterations of 16777216..33554432: 498 odd; 502 even Stats for 1000 iterations of 33554432..67108864: 458 odd; 542 even Stats for 1000 iterations of 67108864..134217728: 500 odd; 500 even Stats for 1000 iterations of 134217728..268435456: 499 odd; 501 even Stats for 1000 iterations of 268435456..536870912: 480 odd; 520 even Stats for 1000 iterations of 536870912..1073741824: 512 odd; 488 even Stats for 1000 iterations of 1073741824..2147483648: 487 odd; 513 even Stats for 1000 iterations of 2147483648..4294967296: 492 odd; 508 even Stats for 1000 iterations of 4294967296..8589934592: 0 odd; 1000 even Stats for 1000 iterations of 8589934592..17179869184: 0 odd; 1000 even Stats for 1000 iterations of 17179869184..34359738368: 0 odd; 1000 even Stats for 1000 iterations of 34359738368..68719476736: 0 odd; 1000 even Stats for 1000 iterations of 68719476736..137438953472: 0 odd; 1000 even Stats for 1000 iterations of 137438953472..274877906944: 0 odd; 1000 even Stats for 1000 iterations of 274877906944..549755813888: 0 odd; 1000 even Stats for 1000 iterations of 549755813888..1099511627776: 0 odd; 1000 even Stats for 1000 iterations of 1099511627776..2199023255552: 0 odd; 1000 even Stats for 1000 iterations of 2199023255552..4398046511104: 0 odd; 1000 even Stats for 1000 iterations of 4398046511104..8796093022208: 0 odd; 1000 even Stats for 1000 iterations of 8796093022208..17592186044416: 0 odd; 1000 even Stats for 1000 iterations of 17592186044416..35184372088832: 0 odd; 1000 even Stats for 1000 iterations of 35184372088832..70368744177664: 4 odd; 996 even Stats for 1000 iterations of 70368744177664..140737488355328: 4 odd; 996 even Stats for 1000 iterations of 140737488355328..281474976710656: 5 odd; 995 even Stats for 1000 iterations of 281474976710656..562949953421312: 20 odd; 980 even Stats for 1000 iterations of 562949953421312..1125899906842624: 34 odd; 966 even Stats for 1000 iterations of 1125899906842624..2251799813685248: 66 odd; 934 even Stats for 1000 iterations of 2251799813685248..4503599627370496: 141 odd; 859 even Stats for 1000 iterations of 4503599627370496..9007199254740992: 272 odd; 728 even Stats for 1000 iterations of 9007199254740992..18014398509481984: 0 odd; 1000 even Stats for 1000 iterations of 18014398509481984..36028797018963968: 0 odd; 1000 even Stats for 1000 iterations of 36028797018963968..72057594037927936: 0 odd; 1000 even Stats for 1000 iterations of 72057594037927936..144115188075855872: 0 odd; 1000 even Stats for 1000 iterations of 144115188075855872..288230376151711744: 0 odd; 1000 even Stats for 1000 iterations of 288230376151711744..576460752303423488: 0 odd; 1000 even Stats for 1000 iterations of 576460752303423488..1152921504606846976: 0 odd; 1000 even Stats for 1000 iterations of 1152921504606846976..2305843009213693952: 0 odd; 1000 even Stats for 1000 iterations of 2305843009213693952..4611686018427387904: 0 odd; 1000 even As any good engineer who's baffled would say: hmmm, that's interesting.