Silnia - rozkład na czynniki pierwsze

[Elayne]

Załóżmy że za pomocą funkcji możemy policzyć dokładną wartość silni dla dowolnej liczby całkowitej nieujemnej. Mamy jakąś tam liczbę calkowitą nieujemną, z twierdzenia Wilsona wychodzi że jest to liczba złożona. Czy można ustalić np. za pomocą silni przez jakie czynniki liczba dzieli się bez reszty?

[Ponewor]

Wyraź się jaśniej jeśli łaska.

[Elayne]

Ciekawi mnie czy za pomocą silni można dokonac faktoryzacji dowolnej liczby złożonej np. klucza RSA

[bartek118]

Załóżmy że za pomocą funkcji możemy policzyć dokładną wartość silni dla dowolnej liczby całkowitej nieujemnej.

Nie trzeba tego zakładać; wiemy to tą funkcją jest... silnia, lub jak kto woli funkcja \(\displaystyle{ \Gamma}\).

Mamy jakąś tam liczbę calkowitą nieujemną, z twierdzenia Wilsona wychodzi że jest to liczba złożona.

Od kiedy jakaś tam liczba całkowita nieujemna musi być złożona!?

Czy można ustalić np. za pomocą silni przez jakie czynniki liczba dzieli się bez reszty?

To pytanie nie ma sensu.

Ciekawi mnie czy za pomocą silni można dokonac faktoryzacji dowolnej liczby złożonej np. klucza RSA

To także.

[Hydra147]

Mam wrażenie, że koledze chodziło o taki problem:
Załóżmy, że mamy algorytm, który jest w stanie policzyć nam silnię jakiejś liczby całkowitej dodatniej w czasie zerowym. Czy z pomocą tego algorytmu możemy stworzyć algorytm, który dokona faktoryzacji liczby całkowitej dodatniej na czynniki pierwsze szybciej niż te obecnie istniejące?
I zapewne przy tworzeniu takiego algorytmu chciał skorzystać z twierdzenia Wilsona. Obawiam się niestety, że taki algorytm nie istnieje z powodu wielkości liczb, jakimi są silnie liczb naturalnych.

[Elayne]

Jeśli potraktować literalnie silnię to jedynym rozwiązaniem jest mnożenie kolejnych liczb by móc obliczyć kolejną silnię. A CZYM DOKŁADNIE JEST SILNIA? Jeśli przyjrzymy się to silnię można potraktować jaką grupę funkcji, im większa silnia tym większa grupa kolejnych funkcji. Wystarczy wykonanie mniej niż sto podstawowych działań algebraicznych plus cztery porównania by móc policzyć dowolną silnię z liczby całkowitej dodatniej i sprawdzenie poprawność obliczeń - jak na razie sprawdza się to bez zarzutu. Problemem jest wykonywanie działań na tak wielkimi liczbami

Nie napisałem że liczba całkowita nieujemna musi być złożona.
Nie uważam tego za bezsensowne.

[a4karo]

Masz kłopoty z precyzyjnym wyrażaniem się: silnia to nie grupa funkcji, tylko jedna funkcja określona na zbiorze liczb naturalnych. Z tego powodu nie może być ani większa, ani mniejsza.

Stwierdzenie

Wystarczy wykonanie mniej niż sto podstawowych działań algebraicznych plus cztery porównania by móc policzyć dowolną silnię z liczby całkowitej dodatniej

wydaje się co najmniej ryzykowne. Chyba że sprawdziłes do 30, no może 35. Ale kryptografia ma raczej w nosie takie małe liczby.

Nie napisałem że liczba całkowita nieujemna musi być złożona.

Ależ napisałeś: przeczytaj swój pierwszy post jeszcze raz, i jeszcze raz ...

[Elayne]

Moim zdaniem by móc policzyć wartość silni dla danej liczby możemy potraktować silnię jako grupę funkcji kwadratowych. Przykładowo dla 5! mamy taki zbiór funkcji:

funkcja1: \(\displaystyle{ f(x)= -x^{2}+121x - punkty (1,120), (120,120)}\)

funkcja2:\(\displaystyle{ f(x)= -x^{2}+62x - punkty (2,120), (60,120)}\)

funkcja3:\(\displaystyle{ f(x)= -x^{2}+43x - punkty (3,120), (40,120)}\)

funkcja4:\(\displaystyle{ f(x)= -x^{2}+34x - punkty (4,120), (30,120)}\)

funkcja5:\(\displaystyle{ f(x)= -x^{2}+29x - punkty (5,120), (24,120)}\)

1)\(\displaystyle{ a=1, c=0}\)
2) b - jeśli jest liczbą:
- parzystą to mamy do czynienia z ciągiem: \(\displaystyle{ 1,3,5,7,9,11}\)
- nieparzystą to mamy do czynienia z ciągiem: \(\displaystyle{ 2,4,6,8,10}\)
Wydaje się że tylko dla funkcji znajdującej się najbliżej środka, w tym przykładzie dla funkcja5 możliwe jest tak sprecyzować warunki by pozwalały jednoznacznie określić postać poszukiwanej funkcji dla danej silni którą chcemy obliczyć. Zaraz ktoś powie że podobny układ funkcji jest wcześniej dla liczby \(\displaystyle{ 60}\)- owszem, z tą różnicą że układ ten nie spełnia m.in. warunku: \(\displaystyle{ 4k=4d^{2}+4p}\).
W ten sposób można prawdopodobnie policzyć i przedstawić każdą \(\displaystyle{ n!}\) dla \(\displaystyle{ n>3}\)

Wrócę na chwilę do mojego nieszczęsnego zdania z pierwszego postu:
Mamy jakąś tam liczbę całkowitą nieujemną, z twierdzenia Wilsona wychodzi że jest to liczba złożona.
Ujmę to inaczej: mam losową liczbę np: \(\displaystyle{ 978224881}\) - nie wiem czy jest to liczba pierwsza czy złożona chyba że wykonam test na pierwszość liczb. Jeśli mam możliwość policzenia silni z takiej liczby to mogę skorzystać z twierdzenia Wilsona i za pomocą tylko jednego dzielenia jednoznacznie określić czy dana liczba jest liczbą pierwszą czy też liczbą złożoną (podana tu liczba jest liczbą pierwszą).

[a4karo]

Podajesz jakieś funkcje, które posłużą do obliczenia 5!, ale nie podajesz żadnego algorytmu w jaki sposób te funkcje tworzyć dla dowolnego n (nawet nie mówisz dlaczego akurat takie funkcje wybierasz do policzenia 5!). Może one są takie właśnie, bo gdzieś tam przyjmują wartość 120? A to by znaczyło, że najpierw znasz wartość 5!, a potem ją obliczasz. Trochę bez sensu.

Szczerze mówiąc, absolutnie nic nie rozumiem z akapitu, który następuje po wylistowaniu tych pięciu funkcji i nadal nie wiem, w jaki sposób maja one posłużyć do obliczenia 5!.

Poza tym musiałbys udowodnić, że algorytm liczenia tych funkcji jest efektywniejszy, niż znane algorytmy liczenia silni.

Z ciekawości spytam: czy pierwszość liczby 978224881, którą przywołujesz, obliczyłeś swoim algorytmem? Ile funkcji do tego użyłeś?

[yorgin]

Moim zdaniem

[...]

Wydaje się

[...]

można prawdopodobnie

Trochę dużo tych niepewności.

policzyć i przedstawić każdą \(\displaystyle{ n!}\) dla \(\displaystyle{ n>3}\)

Po co? Zamiast wykonać (słownie) pięć mnożeń do policzenia \(\displaystyle{ 5!}\), muszę znaleźć (słownie) pięć funkcji, w sumie nie wiadomo po co.

Poza tym szukanie tych funkcji przypomina nieco błędne koło - w końcu wyznaczasz te funkcje w oparciu o wartości silni, a chyba po to te funkcje są Ci potrzebne? Tutaj zgadzam się istotnie z a4karo.

[Elayne]

Ogólny opis: I ćwiartka kartezjańskiego układu współrzędnych. Na początku liczona jest odległość pomiędzy dwoma punktami paraboli dla danego \(\displaystyle{ x}\), dla \(\displaystyle{ x = 5}\) jest to \(\displaystyle{ 18}\). Teraz określamy do której funkcji należy ten odcinek. Jest to liczba parzysta więc należy on do ciągu \(\displaystyle{ 2, 4, 6, 8, 10, 12, 14, 16, 18}\). Wiemy że jeśli przesuniemy odcinek o \(\displaystyle{ 1}\) w prawo to długość odcinka zmniejszy się o \(\displaystyle{ 2}\). Więc jeśli przesuniemy odcinek o \(\displaystyle{ 9}\) pozycji w prawo to otrzymamy wierzchołek poszukiwanej funkcji. W takim razie \(\displaystyle{ b = (5+9)2 + 1 = 29}\) więc funkcja ma postać \(\displaystyle{ f(x) = -x^{2} + 29x}\). Obliczamy teraz funkcję dla \(\displaystyle{ x=5}\), otrzymany wynik jest jednocześnie poszukiwaną wartością silni. Jeśli chcemy to możemy teraz określić pozostałe funkcje tworzące grupę: wiemy przez jakie punkty przechodzą funkcje oraz to że wierzchołki tych funkcji są jednocześnie punktami przecięcia z \(\displaystyle{ f(x)=x^{2}}\)
Dla małych liczb otrzymuje poprawny wynik jeśli nie zrobiłem gdzieś błędu w obliczeniach. Czy to się sprawdza dla dużych liczb tego nie wiem, zresztą nie miałbym za bardzo jak to sprawdzić. Przyjmuje założenie że jeśli coś działa dla małych liczb powinno też działać dla dużych liczb w ściśle uporządkowanym zbiorze funkcji.

[bakala12]

ny opis: I ćwiartka kartezjańskiego układu współrzędnych. Na początku liczona jest odległość pomiędzy dwoma punktami paraboli dla danego \(\displaystyle{ x}\), dla \(\displaystyle{ x = 5}\) jest to \(\displaystyle{ 18}\). Teraz określamy do której funkcji należy ten odcinek. Jest to liczba parzysta więc należy on do ciągu \(\displaystyle{ 2, 4, 6, 8, 10, 12, 14, 16, 18}\). Wiemy że jeśli przesuniemy odcinek o \(\displaystyle{ 1}\) w prawo to długość odcinka zmniejszy się o \(\displaystyle{ 2}\). Więc jeśli przesuniemy odcinek o 9 pozycji w prawo to otrzymamy wierzchołek poszukiwanej funkcji. W takim razie b\(\displaystyle{ = (5+9)2 + 1 = 29}\) więc funkcja ma postać \(\displaystyle{ f(x) = -x^{2} + 29x}\). Obliczamy teraz funkcję dla \(\displaystyle{ x=5}\), otrzymany wynik jest jednocześnie poszukiwaną wartością silni.

Można jaśniej? Zasadniczo to się kupy nie trzyma i ni jak nie wiadomo o co chodzi...

Dla małych liczb otrzymuje poprawny wynik jeśli nie zrobiłem gdzieś błędu w obliczeniach. Czy to się sprawdza dla dużych liczb tego nie wiem, zresztą nie miałbym za bardzo jak to sprawdzić. Przyjmuje założenie że jeśli coś działa dla małych liczb powinno też działać dla dużych liczb w ściśle uporządkowanym zbiorze funkcji.

Przykro mi bardzo, ale widać, po stawianiu takich właśnie założeń, że nie miałeś styczności z poważniejszą matematyką... Bo w matematyce często się zdarza, że jak coś działa dla małych liczb, to działa też dla dużych, ale to trzeba udowodnić. Jednakże, w matematyce zdarzają się niestety niesamowite cuda i coś się popsuje dla jakiejś dużej liczby i już nie zadziała. Sprawdzenia dla dużych liczb można wykonywać za pomocą komputera, ale do pełnej poprawności konieczny jest formalny dowód. W każdym bądź razie ja tutaj nie wiem nawet co mam sprawdzać, więc jak tu cokolwiek udowadniać?

[Hydra147]

Jednakże, w matematyce zdarzają się niestety niesamowite cuda i coś się popsuje dla jakiejś dużej liczby i już nie zadziała.

Idealnym tego przykładem jest hipoteza Pólyi, dla której kontrprzykład jest rzędu \(\displaystyle{ 1,845 \cdot 10^{361}}\) (a taki przynajmniej był pierwotnie).

[yorgin]

Analiza "opisu":

Na początku liczona jest odległość pomiędzy dwoma punktami paraboli

Jakiej paraboli?

dla danego \(\displaystyle{ x}\), dla \(\displaystyle{ x = 5}\) jest to \(\displaystyle{ 18}\).

Skąd to \(\displaystyle{ 18}\)?

Teraz określamy do której funkcji należy ten odcinek.

Jaki odcinek?

Jest to liczba parzysta więc należy on do ciągu \(\displaystyle{ 2, 4, 6, 8, 10, 12, 14, 16, 18}\).

Która liczba? Co, gdy nie jest ona całkowita?

Wiemy że jeśli przesuniemy odcinek o \(\displaystyle{ 1}\) w prawo to długość odcinka zmniejszy się o \(\displaystyle{ 2}\).

Jakiego odcinka? Dlaczego o \(\displaystyle{ 2}\)?

Więc jeśli przesuniemy odcinek o \(\displaystyle{ 9}\) pozycji w prawo to otrzymamy wierzchołek poszukiwanej funkcji.

Dlaczego nie zmniejszy się o \(\displaystyle{ 18}\)? Otrzymamy wierzchołek czego?

W takim razie \(\displaystyle{ b = (5+9)2 + 1 = 29}\) więc funkcja ma postać \(\displaystyle{ f(x) = -x^{2} + 29x}\).

Skąd dodajemy \(\displaystyle{ 1}\)? Czy zawsze dodajemy \(\displaystyle{ 1}\)?

Obliczamy teraz funkcję dla \(\displaystyle{ x=5}\), otrzymany wynik jest jednocześnie poszukiwaną wartością silni.

Funkcji się nie oblicza. Oblicza się wartość funkcji w punkcie.

Jeśli chcemy to możemy teraz określić pozostałe funkcje tworzące grupę: wiemy przez jakie punkty przechodzą funkcje

Skąd to wiemy?

oraz to że wierzchołki tych funkcji są jednocześnie punktami przecięcia z \(\displaystyle{ f(x)=x^{2}}\)

I to?

Dla małych liczb otrzymuje poprawny wynik jeśli nie zrobiłem gdzieś błędu w obliczeniach.

"Jeśli"?

Czy to się sprawdza dla dużych liczb tego nie wiem, zresztą nie miałbym za bardzo jak to sprawdzić.

Masz - od tego jest matematyka.

Przyjmuje założenie że jeśli coś działa dla małych liczb powinno też działać dla dużych liczb w ściśle uporządkowanym zbiorze funkcji.

Założenie istotnie błędne.

[27182818285]

Sposób jest logiczny ale pracochłonny ponad miarę.Patrz poszukiwanie wspólnego dzielnika.W tym wypadku danej liczby i jej silni ( która zawiera w sobie iloczyn kolejnych liczb pierwszych, a więc wszystkich możliwych dzielników). Zamiast silni można się ograniczyć do iloczynu liczb pierwszych mniejszych od pierwiastka z danej liczby. Można również stosować iloczyny pewnego przedziału ciągu liczb pierwszych, ale w sumie to ta sama praca tylko mniejsze liczby dla komputera.W tej metodzie ilpść prób jast i tak maksymalna.