mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Miscellaneous Math (https://www.mersenneforum.org/forumdisplay.php?f=56)
-   -   Why this code converge? (https://www.mersenneforum.org/showthread.php?t=26939)

RomanM 2021-07-29 18:39

-How does the refrigerator work?
-Grmmmmmmmmmm
Old joke.
b=mod(u^n,p); a=mod(b^n,p)
b^2-a is a multiple of p for any integer n>0, I don't know the behavior of epsilon for every n, but seems that algorithm work only if n=2.

charybdis 2021-07-29 18:48

[QUOTE=RomanM;584325]b=mod(u^n,p); a=mod(b^n,p)
b^2-a is a multiple of p for any integer n>0, I don't know the behavior of epsilon for every n, but seems that algorithm work only if n=2.[/QUOTE]

Try going through the same calculations that I did, but with n=3 and the square roots replaced with cube roots. Can you see where things change?

RomanM 2021-07-29 19:24

) we start from (b-y)^2? For cube, (b-y)^3 must be expanded (b^3-3*b^2*y+3*b*y^2-y^3) and solved in whole by the same manner, without any simplification from the start. And I'm stuck with imaginary parts and 3-roots)) At the same time, cube and highger have solution, just like square!

charybdis 2021-07-29 19:55

Going back to this:

[QUOTE=Viliam Furik;584102]Could you explain, what it is supposed to do, what does it do, and what is the question?[/QUOTE]

Please can you explain, in full, what your algorithm actually is for higher n? You haven't made it clear which of the squares stay as squares and which change to n-th powers.

What is the question for higher n? Is there even a question?

RomanM 2021-07-30 10:30

Once again, it's heuristic! There need a genius to shed the light why it work!

For higher orders, I have no working code. This is not mean that is impossible.

charybdis 2021-07-30 13:14

[QUOTE=RomanM;584385]Once again, it's heuristic! There need a genius to shed the light why it work![/QUOTE]

Yes, it's heuristic, but why do you need a proof? Integer factorization algorithms often have a probabilistic element to them: in the quadratic sieve, how do you know you're actually going to find enough smooth numbers?

You've got the code, you can check whether the heuristic fits the numerical evidence. If you solve my exercise about the expected descent rate from a few posts back, that will give you a hypothesis to test.

RomanM 2021-07-30 18:22

First, I dont know whether its well known or new. Second - the spirit of this place! And third, connected with second, plenty of unborn ideas glimpse close to our sight, here I can catch them. Thank You very much for your epsilon!

Batalov 2021-07-30 23:11

[QUOTE=RomanM;584325]-How does the refrigerator work?
-Grmmmmmmmmmm
Old joke.
[/QUOTE]
Refrigerator can easily do 'Grmmmmmmmmmm' and [B]not [/B]work actually.

[QUOTE="Ilf & Petrov"]У колодца мадам Боур была приветствована соседом, Виктором Михайловичем Полесовым, гениальным слесарем-интеллигентом, который набирал воду в бидон из-под бензина. У Полесова было лицо оперного дьявола, которого тщательно мазали сажей перед тем, как выпустить на сцену.

... Виктор Михайлович собрался было уже слезть и обревизовать свою загадочную машинку, но она дала вдруг задний ход и, пронеся своего создателя через тот же туннель, остановилась на месте отправления — посреди двора, ворчливо ахнула и взорвалась. Виктор Михайлович уцелел чудом и из обломков мотоцикла в следующий запойный период [B][I]устроил стационарный двигатель, который был очень похож на настоящий двигатель, но не работал.[/I][/B][/QUOTE]

[QUOTE="https://translate.google.com/"]... Viktor Mikhailovich was about to get off and turn over his mysterious car, but it suddenly backed up and, carrying its creator through the same tunnel, stopped at the place of departure - in the middle of the yard, gasped gruffly and exploded. Viktor Mikhailovich miraculously survived and from the wreckage of a motorcycle in the next drunken period [I][B]he arranged a stationary engine, which was very similar to a real engine, but did not work.[/B][/I][/QUOTE]

Dr Sardonicus 2021-07-31 02:13

[QUOTE=RomanM;584325]<snip>
b=mod(u^n,p); a=mod(b^n,p)
[color=red]b^2-a[/color] is a multiple of p for any integer n>0, I don't know the behavior of epsilon for every n, but seems that algorithm work only if n=2.[/QUOTE]Do you mean b^n - a?

Another issue arises if n > 2, particularly for odd n > 2. Even if p is prime, if gcd(n, p-1) = 1, [i]every[/i] residue mod p is an n[sup]th[/sup] power residue. For n = 3, this is the case for every prime p congruent to 2 (mod 3).

RomanM 2021-07-31 15:19

[QUOTE=Batalov;584460]Refrigerator can easily do 'Grmmmmmmmmmm' and [B]not [/B]work actually.[/QUOTE]
Of course! And quiet too on Peltier elements) This joke mainly about our understanding of life consciousness
[QUOTE=Dr Sardonicus;584465]Do you mean b^n - a?
[/QUOTE]
No. Talk was about [B]quadratric[/B] case; yes for higher orders.
[QUOTE=RomanM;584239]
***
Take some integer u>sqrt(p), b=mod(u^2,p); a=mod(b^2,p)=mod(u^4,p);

[From (b-y)^2==0 mod p
b^2-2*b*y+y^2==0 mod p or a-2*b*y+y^2==0;
Solution: y=b-sqrt(b^2-a) (and y=b+sqrt(b^2-a), using first)
Make y an integer, and compute t= b-y =ceil(sqrt([B]b^2-a[/B]))]
***
[/QUOTE]
(b-y)^3=b^3-3*b^2*y+3*b*y^2-y^3
if b<sqrt(p) and b^3>p, a=mod(b^3,p)
one roots (of 3)
((-b)^3+a)^(1/3)+b
(b-y)^4
root
(b^4-a)^(1/4)+b
and so on. [B]Other roots[/B] also have importance


All times are UTC. The time now is 21:11.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.