» »

[php] Razbijanje giantskih števil na prafaktorja

[php] Razbijanje giantskih števil na prafaktorja

Yacked2 ::

Živjo, delam program za razbijanje zmnoška dveh izjemno velikih praštevil.
Na primer vhodni podatek je:
7228174241881

Izhodni podatek:
181081
39916801


Do nekega števila moja skripta deluje, potem pa dobil čuden izhodni podatek:
2
9.5601057529824E+15

ta eksponent na koncu mi zmede aplikacijo. Kako bi skripto še bolj optimiziral ?

<?php
$n = 19120211505964799;


$a = 2;
while ($a < $n)
{
	if(bcmod($n,$a)==0)
	{
		break;
	}
	$a++;
}

$p = $a;
$q = $n / $a;

echo $p.'<br>'.$q;

matonson ::

Dve ideji(kaj več ti ne morem pomagati):
- vsa praštevila(razen 2) so liha
- uporaba kakšnega algoritma za praštevila (na hitro Google: https://www.google.si/search?q=Sieve+of......0.0...1c.1.7.psy-ab.nZtpJkO-Epk&pbx=1&bav=on.2,or.r_qf.&fp=b0e0f216920eb835&biw=1920&bih=918 )

Fridolin ::

Namesto, da praštevila sam generiraš, jih morda lahko sparsaš iz kakšne strani, npr. Big Primes

Najenostavnejša optimizacija pa bi bila, da $a namesto za 1 povečuješ za 2 kot je omenjeno zgoraj.

Mavrik ::

ta eksponent na koncu mi zmede aplikacijo. Kako bi skripto še bolj optimiziral ?


Ta eksponent je samo način zapisa števila. Poglej si kako se številke formatirajo no.
The truth is rarely pure and never simple.

Yacked2 ::

Bolj kot hitrost je problem ta eksponent. To je tako kot pri kalkulatorju ko hočeš nekemu velikemu številu odšteti majhno število, sploh nemoreš ker ti zaokoži.
Korak naprej ni vedno ustrezen...sploh če si na robu prepada!

Zgodovina sprememb…

  • spremenil: Yacked2 ()

Pebkac ::

Glede na to da se ti pojavi tisti eksponent, predvidevam da uporabljaš floating point števila. Oziroma je možno da se ti nekje v kodi int pretvori v float, ne poznam phpja tako da ne bi vedel. To je zelo slaba ideja v tem primeru, saj rabiš rezultate, ki morajo biti točno cela števila. Zapomni si, da imajo floating point števila omejeno natančnost (tam nekje prvih 7 števk za float in 15 števk za double). Najboljša rešitev je, če si dobiš kakšno knjižnico, ki omogoča operiranje s poljubno velikimi integerji, in ne uporabljaj številskih tipov ki so že vključeni v programski jezik.

metalc ::

Namesto, da inkrementiraš praštevilske kandidate za 2, lahko stvar še malenkost bolj optimiziraš. Enostavno se da namreč dokazati, da za vsa praštevila večja od 3 velja: p=6*k+1 ali 6*k-1 (seveda ne velja obratno), ali drugače, kandidate izmenično povečuješ za 2 in 4. Sicer pa praštevilski razcep velja za računsko zahtevnega, na čemer konec koncev tudi temelji kriptografija. Celo kripto knjižnice pri res velikih številih samo ocenijo, če je dovolj velika verjetnost, da gre za praštevilo.

Sicer pa preveri, koliko bitna so cela števila pri PHP (po mojem 32 ali 64, kaj lahko je tudi odvisno od OS in HW arhitekture). Ko presežeš to območje, ti najverjetneje stvar pretvori v float z vsemi posledicami omejene natančnosti. Ena rešitev je, da napišeš razred (npr. BigInt) in v njem hraniš velika števila kot polja celih števil. Ali pa greš na jezik, kjer int pravzaprav nima omejitev (z izjemo razpoložljivega pomnilnika), npr. Python.

darkkk ::

samo fyi: vprašanje a nekaj je praštevilo je rešljivo v polinomskem času, razcep (faktorizacija,... ) je časovno zahteven do te mere, da na njemu temelji RSA.

Uglavnem, ne poznam php-ja, ampak se ti splača nek "strong typed" jezik oz. forsirat tipe v takih algoritmih.

technolog ::

$q = $n / $a;


Tudi tu moraš uporabit bc* funkcije, npr:

$q = bcdiv($n, $a);


Koda ti bo potem delala, seveda pa si poglej še vse, kar so napisali ostali.

Yacked2 ::

Ja gre se za razbijanje RSAja...seveda ne takih števil kot jih uporabljajo za kodiranje danes, ampak recimo da bi lahko
19120211505964799 razbil na 39916801 in 479001599.

Našel sem kjižnico GMP a mi jo na WinOS ni ratalo spravit. Sedaj poiskušam s tole http://pear.php.net/package/Math_BigInt...
Korak naprej ni vedno ustrezen...sploh če si na robu prepada!

Yacked2 ::

Evo, sedaj mi deluje, a sedaj je problem, ker se mi prej izteče 30 sekund: Fatal error: Maximum execution time of 30 seconds exceeded in C:\wamp\www\BigInteger.php on line 1354

Kako ta čas prestavim dalj. npr. 10 min ali več...oz rabim boljše generiranje praštevil

skripta:
<?php
include('BigInteger.php');

//stevilo za zlomit
$n = new Math_BigInteger ('19120211505964799');

//začetek zanke na praštevilo 3
$a = new Math_bigInteger('3');

//prvo praštevilo 2
$prvoPrastevilo = new Math_bigInteger('2');

//ker so praštevila liha (razen 2) prištevamo 2
$pristej = new Math_bigInteger('2');

//pogledamo ali je prvo praštevilo 2 
list($quotient,$remainder) = $n->divide($prvoPrastevilo);

if($remainder == '0') //če je deljivo z dva
{
	$N1 = $prvoPrastevilo; //deljitel je N1
}
else //če ni deljivo z dva
{
	while( $a < $n) //začnemo zanko 
	{
		list($quotient,$remainder) = $n->divide($a); //začnemo z 3

		if($remainder=='0') //ko dobimo deljitelja
		{
			$N1 = $a; //deljitelja damo v $N1
			break;
			
		}
	
		$a = $a->add($pristej); //če ni ga povečamo za 2

	}
}

if(!(isset($N1)))
{
	echo $n->toString().' je prastevilo';
}
else
{
	list($N2,$remainder) = $n->divide($N1);
	echo 'Stevilo: '.$n->toString().'<br>Prastevili:<br>'.$N1.'<br>'.$N2;
}


?>
Korak naprej ni vedno ustrezen...sploh če si na robu prepada!

technolog ::

tole daš na vrh kode:

set_time_limit(10*60);

darkkk ::

Še ena opazka :)

Dejansko rabiš furat zanko le do sqrt(n): namreč če imaš netrivialnega delitelja, je vsaj en manjši oz. enak sqrt(n).

V primeru, da veš, da imaš praštevilo (tj, AKS test ali kaj drugega) je itak vseeno do kam daš zanko, ker boš itak našel nekaj preden prideš do korena.

(še link) AKS primality test @ Wikipedia

Zgodovina sprememb…

  • spremenil: darkkk ()

technolog ::

Pa pazi tud to, da sqrt(n) cachiraš v spremenljivko in ne računaš v vsaki iteraciji. Korenjenje BigIntov je počasno.

WarpedGone ::

SQRTja sploh ne računaš ampak ga inkrementiraš in kvadriraš in tako dobivaš mejo, do kam ti velja, predno ga moraš spet inkrementirat in skvadrirat.
Če se že gremo naivno implementacijo :)
Zbogom in hvala za vse ribe

darkkk ::

Pa pazi tud to, da sqrt(n) cachiraš v spremenljivko in ne računaš v vsaki iteraciji. Korenjenje BigIntov je počasno.

Eno tako čist offtopic vprašanje:
Kako recimo c, c++, c# kompajleri delajo, če daš npr. sqrt nečesa v pogoj pa je ta nekaj neodvisen od vsebine zanke? A to zna zoptimizirat al bolj ne? Kaj pa glede ostalih skriptnih jezikov (Matlab, R, python) ?

WarpedGone ::

Verjetnost da znajo pada od leve proti desni tako kot si jih naštel :)
Sicer pa to sam preveriš v par minutah.
Zbogom in hvala za vse ribe

darkkk ::

Ni problem preverit, samo test na "sample of 1" je bolj tkotko. Bolj me je zanimalo, če se kaj ve o kakem iso standardu. O loop unwrapping optimizaciji c++ se je govorilo že 10 let nazaj ampak ...

WarpedGone ::

Ni tle standarda, so le enostavnejše in bol zahtevne optimizacije. Eni stvar terajo dlje,drugi odnehajo prej.
Zbogom in hvala za vse ribe

Yacked2 ::

To z mejo zanke je pomojem mnenju brezvezno, saj se zanka ustavi takoj ko dobim najmanjši prafaktor. V wamppu sem popravil limit na 1 uro, upam da bo dovolj.

To da je praštevilo je verjetnost zelo majhna, saj bo program služil za razbijanje modulov pri RSAju kjer je n = p*q pri katerem velja p !=q ter p,q sta praštevili.

Rezultati...modul sestavljen z najmanjše praštevilo je prvo praštevilo večje kot milijarda razbito v 3 minutah
Korak naprej ni vedno ustrezen...sploh če si na robu prepada!

technolog ::

No, če je število vedno sestavljeno, potem res ne rabiš ustavitvenega pogoja, tako kot si napisal.

Za faktorizacijo drugače obstajajo boljši algoritmi.

Hayabusa ::

50!+1 ti sfaktorira v koliko časa ?

kihc ::

darkkk je izjavil:

O loop unwrapping optimizaciji c++ se je govorilo že 10 let nazaj ampak ...


Ampak? GCC in Intelovi compilerji za C/C++ vem da to podpirajo že lep čas(-03 switch), za ostale pa nevem.
x

Yacked2 ::

Hayabusa je izjavil:

50!+1 ti sfaktorira v koliko časa ?


smešno =D V trenutku....

do 149 res ni daleč
Korak naprej ni vedno ustrezen...sploh če si na robu prepada!

Zgodovina sprememb…

  • spremenil: Yacked2 ()

Hayabusa ::

50!+1 v trenutku ?
You kidding me ?

WarpedGone ::

Ja, v trenutku vrže napako in neha.
Zbogom in hvala za vse ribe

technolog ::

Pa saj je napisal, da je 149 najmanjši prafaktor števila 50! + 1.

Nekdo je hotel bit preveč pameten.

darkkk ::

Bolj zabavno:
Pi = i-to praštevilo.
p = p1*p2*....*p50 +1;
q = p1*...*p51 +1:
faktoriziraj p*q :)

(pomoje je tole še normalno izračunljivo, k so 50. praštevilo je še vedno manjše od recimo 200)

Zgodovina sprememb…

  • spremenil: darkkk ()

Hayabusa ::

technolog je izjavil:

Pa saj je napisal, da je 149 najmanjši prafaktor števila 50! + 1.

Nekdo je hotel bit preveč pameten.

In naslednje številke ?

technolog ::

[rok@rok-laptop ~]$ time factor 30414093201713378043612608166064768844377641568960512000000000001
30414093201713378043612608166064768844377641568960512000000000001: 149 3989 74195127103 6854870037011 100612041036938568804690996722352077

real	0m4.731s
user	0m4.647s
sys	0m0.013s


Se pravi, prafaktorji so:
149
3989
74195127103
6854870037011
100612041036938568804690996722352077

Moj za en jajc laptop je to ugotovil v manj kot 5 sekundah.

Hayabusa ::

Sprašujem prvotno op-a, ne tebe.
S čim si to počel (sw, hw) ?

Zgodovina sprememb…

  • spremenilo: Hayabusa ()

technolog ::

Fora je, da če je več malih prafaktorjev (kot sta 149 in 3989), to ogromno poenostavi problem. Težje je, če sta samo dva velika.

Drugače uporabljen je GNU/linuxov utility factor, ki je vgrajen v skoraj vsako distribucijo: http://linux.die.net/man/1/factor

Laptop je pa en Core 2 duo pr 2.1 GHz.

Zgodovina sprememb…

Hayabusa ::

Kateri distro imaš ? Meni v MS VPC in distro damn small linux 4.4 faktorira samo do 19 mestne številke, potem javi da številka ni "valid positive integer".

Zgodovina sprememb…

  • spremenilo: Hayabusa ()

technolog ::

Ja, poznam ta problem, tudi meni včasih ni hotelo. Ampak sedaj, ko je izšla nova verzija coreutils, zadeva deluje.

https://www.archlinux.org/packages/core...

Probal sem za test 200!, pa deluje normalno.


Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

[Raptor] Razcep na prafaktorje

Oddelek: Šola
242212 (1754) Math Freak
»

pra števila.. (strani: 1 2 )

Oddelek: Znanost in tehnologija
788337 (4676) Yacked2
»

Najhitrejši programski jezik? (strani: 1 2 )

Oddelek: Programiranje
757378 (5198) Senitel
»

Problemi pri C++ programiranju...

Oddelek: Programiranje
363768 (3243) George
»

Kako so ugotovili, da je 2<sup>13466917</sup>-1 praštevilo. (strani: 1 2 )

Oddelek: Znanost in tehnologija
528959 (7462) larpo

Več podobnih tem