Re: OT: Gyufafust -> Primfaktorizáció

[Rancz Lajos]

On Mon, 27 Dec 2004 12:09:09 +0100, Nya'ri Viktor wrote:
>> Nem hiszem, hogy leegyszerűsítés lenne. Nagyon egyszerű
>> rendszerek is tudnak kaotikusan viselkedni. Pl. a linkben adott
>> rendszer is 4 viszonlyag egyszerű egyenletből áll, melyekben egy
>> fifika van, a nemlinearitásuk. Vagy nézzük a Mandelbrot halmazt,
>> az egy tök egyszerű rekurzív összefüggést használ és mégis nagyon
>> bonyolult tulajdonságokat mutat.
>>
>> A lényeg nem az összefüggés hanem az, hogy a kezdeti feltételek
>> nagyban befolyásolják a az eredményt, kis változás a kezdetkor
>> nagy változás a végén.
>>
> Akkor lényegében a múltkor már jól megrágott primfaktorizációnál
> (Vajk Úrtól kaptam is a fejemre :-) ) is ezzel a problémával állunk
> szemben. Mert pl.
>
> m=167 -> 0 osztója van 1-en és önmagán kívül (primszám) m=168 -> 14
> osztója van 1-en és önmagán kívül (ha jól számoltam :-) ) m=169 ->
> 1 osztója van 1-en és önmagán kívül (négyzetszám)
>
> Azaz az m minimális változása esetén (1/m) drasztikusan változik az
> osztók száma és elhelyezkedése is; de akkor az előzményekből az
> következik (legalábbis az én olvasatomban) hogy ezen logika alapján
> a primfaktorizációra is _kell_lenni_ valami kellően bonyolult, de

Igen, az osztók és m között nemlineáris összefüggés van. De ebből nem következik az, hogy ha az egyik irány (m=pq)  könnyű, attól még a másik irány is könnyű. A prímekkel kapcsolatban annyit lehet tudni (sőt az NP beli problemákkal egyetemben), hogy _még_ nem találtak rá polinom idejű algoritmust. De ettől még lehet, meg nem is lehet :-)

Üdv,
	Lajos

> _polinomidőben_ végrehajtható algoritmusnak, nem??? Csodálkozom,
> hogy a mai napig még nem találták meg a megoldást...
>
> V.
>
> -----------------------------------
> Szponzorunk: http://tonerbolt.hu/