faktoryzacja liczby

Kera · Post autor: **Kera** » 5 lut 2015, o 21:17

czy szybko można rozłożyć liczbę \(\displaystyle{ 100496021341}\) , mając tylko dane:
\(\displaystyle{ n=100496021341}\)

\(\displaystyle{ a=634024}\)

\(\displaystyle{ b=586803}\)
z jakich wzorów należy skorzystać ?

Medea 2 · Post autor: **Medea 2** » 5 lut 2015, o 22:45

Jeżeli nie powiesz nam, co oznaczają \(\displaystyle{ n,a,b}\), to szanse są raczej znikome. daje sobie radę.

Elayne · Post autor: **Elayne** » 6 lut 2015, o 01:03

Zaraz tam armatę na wróbla wytaczać, np:
wpisujesz liczbę, enter i jest gotowy wynik \(\displaystyle{ (197299 \cdot 509359)}\).
Pisemnie ok. \(\displaystyle{ 10-15}\) minut potrzeba - rozkład Fermata dla grupy liczb.

Kera · Post autor: **Kera** » 6 lut 2015, o 08:56

Przykład jest specjalnie niski. Interesuje mnie czy na podstawie tych danych, da się obliczyć rozkład tej liczby.Podaj rozwiązanie Elayne, bez podstawiania kolejnej liczby naturalnej do wzoru, bo dla dużych cyfr nie ma to sensu.

Medea 2 · Post autor: **Medea 2** » 6 lut 2015, o 09:47

Nie odpowiedziałaś na moje pytanie - skąd są liczby \(\displaystyle{ a, b}\) i co oznaczają? Czy przykład ma coś wspólnego z RSA?

A, i jeszcze jedno. Liczby to nie cyfry! Największą cyfrą jest \(\displaystyle{ 9}\), największej liczby nie ma.

Kera · Post autor: **Kera** » 6 lut 2015, o 17:19

Liczby \(\displaystyle{ a,b}\) są rezultatem pewnych wzorów.Czy potrafisz Medea 2 na podstawie tylko podanych danych rozwiązać przykład? A gdy już to zrobisz, to czy jest inny sposób, który nie wykorzystuje metody podstawiania kolejnej liczby naturalnej do wzoru.Podaj jaki mam na myśli wzór, lub inną metodą oblicz.

lolks123 · Post autor: **lolks123** » 6 lut 2015, o 17:32

W takim razie równie dobrze można napisać: rozłożyć liczbę \(\displaystyle{ n}\) mając dane:

\(\displaystyle{ n = 100496021341}\)

oraz \(\displaystyle{ a = 1}\), \(\displaystyle{ b = 1}\)

Gdzie a, b są rezultatem pewnych wzorów.

Widzisz już, że to trochę bez sensu? Równe dobrze możesz podać samą liczbę \(\displaystyle{ n}\), bo \(\displaystyle{ a, b}\) tak zdefiniowane niczemu nie służą.

Medea 2 · Post autor: **Medea 2** » 6 lut 2015, o 17:44

Kera pisze:A gdy już to zrobisz, to czy jest inny sposób, który nie wykorzystuje metody podstawiania kolejnej liczby naturalnej do wzoru.

Oczywiście, najwydajniejsze algorytmy nie wykorzystują trial division. Polecam chociażby .

Elayne · Post autor: **Elayne** » 6 lut 2015, o 18:00

Rozłożyć liczbę na czynniki można na wiele sposobów, tutaj akurat skorzystałem z rozkładu Fermata a więc nie da się tego raczej rozwiązać bez podstawiania kolejnych liczb naturalnych do wyrażenia bo na tym m.in. opiera się ta metoda. Nie wiem co oznaczają podane przez Ciebie liczby \(\displaystyle{ a}\) oraz \(\displaystyle{ b}\) dlatego obliczenia bazują na fakcie że znana jest liczba \(\displaystyle{ 100496021341}\) która ma zostać rozłożona na czynniki pierwsze.

\(\displaystyle{ n \cdot b=f \wedge n,b \in \mathbb{N}\wedge 0<n \le b<f \\
f=100496021341 \\
kw=\sqrt{f}=317012 \\
r=kw^{2}-f=586803 \\
tr=kw-\sqrt{r}=316246}\)
\(\displaystyle{ tr}\) jest parzyste to:
\(\displaystyle{ ox=tr-1=316245}\)

\(\displaystyle{ oy = (f - ox) \div 2=50247852548 \\
w = oy \div ox=158889 \\
roxy =oy - ox \cdot w=743}\)

\(\displaystyle{ f(x)=\frac{x^{2}}{2}+767x+743}\)

\(\displaystyle{ f(a)=316245 \cdot a - x \cdot a}\)

\(\displaystyle{ f(x)=f(a) \\
\frac{x^{2}}{2}+767x+743=316245 \cdot a - x\cdot a \\
632490a=x^2+2x\cdot(767+a)+1486}\)

stąd mamy:

\(\displaystyle{ a=36317 \\
x=118946}\)

\(\displaystyle{ n=ox-x \\
n=316245-118946=197299 \\
b=f \div n=100496021341 \div 197299 =509359}\)

Kera · Post autor: **Kera** » 6 lut 2015, o 23:09

Jestem pod wrażeniem Elayne, pytanie tylko czemu nie opracowałeś metody, gdzie szukasz tylko jednej niewiadomej,zamiast dwóch? Moja metoda jest podobna do twojej, ale zdecydowanie bardziej prosta i szuka tylko jednej niewiadomej, a jest nią obliczone przez ciebie \(\displaystyle{ a=36317}\)
Spróbuj Elayne odgadnąć mój wzór mając do dyspozycji wszystkie dane, które zostały użyte w tym temacie.Jak ci się uda, to opiszę swoją metodę.

Elayne · Post autor: **Elayne** » 7 lut 2015, o 00:06

Przyjrzyj się dokładnie, są dwie zmienne ale tylko jednej zmiennej szukasz.
Wiesz co w tym równanie kryje się pod \(\displaystyle{ a}\)? Nie sądzę żeby był inny sposób w którym by wyszło \(\displaystyle{ a=36317}\) - można wręcz rzec że jest to liczba losowa.

Kera · Post autor: **Kera** » 7 lut 2015, o 00:24

Jesteś w błędzie Elayne, nie jest to liczba losowa, a inny sposób istnieje ,ponieważ na nim operuję.
Może się mylę, ale musisz znaleźć swoje \(\displaystyle{ a,x}\) aby rozwiązać swoje równanie!
wiem co kryje \(\displaystyle{ a}\) ,ale na razie to przemilczę.

Elayne · Post autor: **Elayne** » 7 lut 2015, o 00:31

Z tego co wiem można ten układ równań rozwiązać na cztery różne sposoby.
Jest to suma reszt z dzielenia dla grupy liczb - wystarczy że zmienisz układ o \(\displaystyle{ 1}\), wtedy \(\displaystyle{ a}\) ma zupełnie inną wartość.

Kera · Post autor: **Kera** » 7 lut 2015, o 00:39

Zależność \(\displaystyle{ a}\) jest od dzielników liczby i pierwiastka.
np:
\(\displaystyle{ 197820057767642726943619}\)
razy
\(\displaystyle{ 205564669856157031177963}\)

\(\displaystyle{ a=37175765741767229594}\)

Elayne · Post autor: **Elayne** » 7 lut 2015, o 00:52

Mylisz się. Zmienna \(\displaystyle{ a}\) zależna jest od przyjętej wielokrotności w funkcji kwadratowej.