Why this code converge?

[RomanM]

-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]

Originally Posted by RomanM

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.

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]

) 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]

Going back to this:

Originally Posted by Viliam Furik

Could you explain, what it is supposed to do, what does it do, and what is the question?

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]

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]

Originally Posted by RomanM

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

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]

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]

Originally Posted by RomanM

-How does the refrigerator work?
-Grmmmmmmmmmm
Old joke.

Refrigerator can easily do 'Grmmmmmmmmmm' and not work actually.

Originally Posted by Ilf & Petrov

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

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

Originally Posted by 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 he arranged a stationary engine, which was very similar to a real engine, but did not work.

[Dr Sardonicus]

Originally Posted by RomanM

<snip>
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.

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, every residue mod p is an n^th power residue. For n = 3, this is the case for every prime p congruent to 2 (mod 3).

[RomanM]

Originally Posted by Batalov

Refrigerator can easily do 'Grmmmmmmmmmm' and not work actually.

Of course! And quiet too on Peltier elements) This joke mainly about our understanding of life consciousness

Originally Posted by Dr Sardonicus

Do you mean b^n - a?

No. Talk was about quadratric case; yes for higher orders.

Originally Posted by RomanM

***
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^2-a))]
***

(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. Other roots also have importance