Mi a leghatékonyabb algoritmus, hogy nagyon nagy számokat felírjunk p + q1 * q2 alakban?

Mi neked a nagyon nagy szám? 20, 100 vagy 1000-jegyű?

Random számok, vagy egymást követőek? Párosak, vagy páratlanok? Utóbbi esetben valamelyik prím a 2 lesz.

Általánosságban: arra kell törekedni, hogy p, mint kiadódó szám, kicsi legyen, így sokkal nagyobb valószínűséggel prím.

Tehát, vagy az n/2 alatti prímekkel kell próbálkozni, vagy az n/3, n/5, n/7, n/11, ... alatti prímet kell megkeresni.

Csak akkor lesz igazán hatékony, ha egymást követő számok felbontását keresed.

"Általánosságban: arra kell törekedni, hogy p, mint kiadódó szám, kicsi legyen, így sokkal nagyobb valószínűséggel prím."

A k kitalált szám esetében adott p prím esetében a k-p kell vizsgálni hogy k-p összetett szám e, ha igen akkor ez 2 prímszám szorzata e. Ha k nagy és p kicsi és k-p = q1*q2 akkor nehéz faktorizálni akkor ha q1*q2 "erős" prímszámok. Viszont akár könnyű is lehet abban az esetben például ha q1 q2 közül az egyik kicsi vagy akkor ha q1 és q2 számok a szorzatuk négyzetgyökéhez van elég közel.

Tudom hogy sok volt a "ha ... akkor", viszont közel sem mondanám hogy az a leghatékonyabb amit felvázoltál. Illetve csak adott esetekben hatékony amit felvázoltál.

Mivel általános esetben ellenőrizni, hogy prím-e sokkal könnyebb feladat mint faktorizálni. Ezért nagy k esetében hatékony lehet nagy p-t keresni ahol k-p számot könnyű faktorizálni.

Mivel még a P=NP probléma is a matemaika egyik megoldatlan problémája, így itt a leghatékonyabb algoritmus megtalálása ami bizonyítható is hogy az kétséges, hogy bárki be tudná biztonyítani ha meg is találná a leghatékonyabb algoritmust. Továbbá gondolom sebességre a leghatékonyabbra kíváncsi a kérdező, mert az sem egy definiált fogalom hogy leghatékonyabb milyen szempontból leghatékonyabb. (Lehetne memória szempontjából is, hogy legkevesebb memóriát használ.)