Matematické Fórum

Mkok · 18. 10. 2014 22:19 — Editoval Mkok (18. 10. 2014 22:28)

Zdravím, zasekl jsem se na jednom problému a potřeboval bych trochu pomoct.

Mám nějaké číslo n o kterém vím že je mocninou jednoho prvočísla. Potřebuji efektivní způsob jak najít toto prvočíslo a jeho mocninu.

t.j. vyřešit rovnici

$n=p^{a}$

když znám , a vím že je prvočíslo.

Efektivním způsobem myslím algoritmus běžící v polynomiálním čase vzhledem k n.

Jediné co mě napadá je počítat prvočíselné odmocniny z čísla n, a zkoušet zda jsou celočíselné. Bohužel však vůbec nevím jestli existuje efektivní algoritmus pro počítání n-té odmocniny z čísla, a i kdyby existoval, tak by se prakticky jednalo o pokus o faktorizaci čísla a na rozklad prvočísel. Což by nejspíše nebylo efektivní.

Díky,

check_drummer · 18. 10. 2014 23:23

↑ Mkok:
Ahoj, faktorizace čísla na prvnočísla je podle mého polynomiální vzhledem k n...

Brano · 19. 10. 2014 18:26 — Editoval Brano (19. 10. 2014 19:56)

podla mna sa to za zadanych podmienok da robit v case $\log n$ (co by bol najhorsi pripad niekedy aj lepsie)

Totizto mas ohranicenie, ze $\alpha\le \log_2 n$ . Takze mozes to robit nejak takto:

funkcia(n)
{
pre k=2 .. log_2(n) testuj ci m=n^(1/k) je cele cislo ak ano tak vrat

alpha = k*funkcia(m).alpha
p = funkcia(m).p

inak vrat

alpha = 1
p = n
}

teda dufam ze som to nezmrvil, ale idea by mala byt jasna

este k tomu odmocneniu - to staci priblizne vypocitas trebars a=exp(log(n)/k) - zaokruhlene nadol a skusis ci plati a^k<n a (a+1)^k>n ak ano tak potom ta odmocnina nie je celociselna - no asi chapes ideu

ak ale nemas logaritmicke tabulky/funkciu k dispozicii, tak mozes skusit newtonovu metodu

kompik · 23. 10. 2014 14:17

* Wikipedia: Detecting perfect powers
* MathOverflow: how to quickly determine whether a given natural number is a power of any other natural number?
* cstheory.SE: How to check if a number is a perfect power in polynomial time

A keď už vieš kľúčové slová, tak pomocou nich určite nájdeš kopec ďalších vecí online.

kompik · 23. 10. 2014 19:49

Brano napsal(a):
podla mna sa to za zadanych podmienok da robit v case $\log n$ (co by bol najhorsi pripad niekedy aj lepsie)

Ja pre istotu upozorním, že informatici a podobné živočíšne druhy chápu zložitosť zvyčajne nie ako počet vykonaných matematických operácií, ktoré sa urobia, ale berú do úvahy aj to, že sčitovanie, násobenie, umocňovanie (v tomto prípade odmocnina) trvajú dlhšie. (Potrebujú vykonať viac inštrukcií procesora.)

Matematické Fórum

#1 18. 10. 2014 22:19 — Editoval Mkok (18. 10. 2014 22:28)

Faktorizace mocniny prvočísla

#2 18. 10. 2014 23:23

Re: Faktorizace mocniny prvočísla

#3 19. 10. 2014 18:26 — Editoval Brano (19. 10. 2014 19:56)

Re: Faktorizace mocniny prvočísla

#4 23. 10. 2014 14:17

Re: Faktorizace mocniny prvočísla

#5 23. 10. 2014 19:49

Re: Faktorizace mocniny prvočísla

Brano napsal(a):

Zápatí