Złożoność bardzo dużej liczby.

[Kera]

Witam
Jak udowodnić że liczba \(\displaystyle{ 10^{ 10^{8}-1 }+13}\) jest złożona, mimo że uważam że może być pierwsza. Czy test Millera-Rabina w ogóle podołałby czasowo???

[Brombal]

Test Millera-Rabina dla \(\displaystyle{ 10^{ 10^{8}-1 }+13}\) na dobrym sprzęcie potrwa ponad 6-8 miesięcy. Na arcy-sprzęcie pewnie z parę tygodni. Zauważ, że liczba ma mniej niż \(\displaystyle{ 10^8}\) cyfr i nie kwalifikuje się do nagrody.

[Kera]

Brombal liczba ta ma równo \(\displaystyle{ 10 ^{8}}\)cyfr, (jedynka z przodu i \(\displaystyle{ 10^{10^{8}-1}}\) zer), czyli łącznie \(\displaystyle{ 10 ^{8}}\) cyfr. Jak dla mnie \(\displaystyle{ 10 ^{2}}\) to jedynka i dwa zera czyli łącznie trzy cyfry. Hmm, chyba sie nie mylę???

[Brombal]

Nie mylisz się . Ale nie sprawdziłeś czy w regulaminie konkursu nie jest tak - " ...ponad 100 mln cyfr...".

[Kera]

pisze "z najmniej 100 milionami cyfr", ale możliwe że masz rację, choć nie jestem tego pewien.