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-06-23 15:40

Why this code converge?

p- any composite number
for small p, inner loop may be less than 250, its heuristic)

[CODE]{p=1237*1234577; c=ceil(sqrt(p));
for(n=c,c+10000,
b=lift(Mod(n^2,p));a=lift(Mod(b^2,p));
for(y=1,250,
t=ceil(sqrt(b^2-a));
b=lift(Mod(t^2,p));a=lift(Mod(b^2,p));
if(b<c,break());); localprec(7); b=b/c/1.; if(b<.1,print(b);););}[/CODE]

Regards,
Roman

 RomanM 2021-06-23 18:35

Easy to see that t in this code is coordinate of the lower point of some "theeth of the saw" on the graf x^2 mod p. (t-1 upper)
In second cycle we just make jumps to next such "theeth" and go on. Curiosly, this process have two outcome - some closed loop, ring, and zero, or sub sqrt value of t^2 mod p one "jump" before.
I dont known, new or old one this heuristic. But its look like a sieve for n values, and hypothetically can point out on the some dependency in x^2 mod p

 RomanM 2021-06-25 13:06

Most interesting, we can try the same method (saw jumps) for x^a mod p, when a>2, and (with hope) find such x, x^a mod p <p^(-a)
Dreams, only dreams of course)) The curse of sqrt too strong.

 RomanM 2021-07-22 14:05

Once again, Why does it work? (Personally I don't know yet))

[CODE]
\p300
{p=233108530344407544527637656910680524145619812480305449042948611968495918245135782867888369318577116418213919268572658314913060672626911354027609793166341626693946596196427744273886601876896313468704059066746903123910748277606548649151920812699309766587514735456594993207;
c=ceil(sqrt(p));
for(n=1,p,
u=c+n; \\initial values
b=lift(Mod(u^2,p));
a=lift(Mod(b^2,p));

for(y=1,250, \\The riddle is here, in this cycle.

t=ceil((b^2-a)^(1/2));
b=lift(Mod(t^2,p));
a=lift(Mod(b^2,p));

if(b<c, break());); \\break at sub sqrt residual
localprec(7);
z=(b/c/1.);
if(z<1,print(z," ",t));
);}
[/CODE]

 RomanM 2021-07-27 19:06

No one here? I'm talking with themselves)) Let [B]p[/B]=p+1260, and for the same t from code above, residuals will be *slight* different, and[B] p[/B] is prime.
How small can be residuals in this case?
Or by other word, why we can't find the small residuals for prime [B]p[/B], and they still small for our composite p?

 Viliam Furik 2021-07-27 19:34

Okay, I'm here. I've been watching occasionally since the first post.

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

 RomanM 2021-07-27 19:41

Factorization of numbers.

 Viliam Furik 2021-07-27 19:58

[QUOTE=RomanM;584104]Factorization of numbers.[/QUOTE]

That's too vague.

1. What is it supposed to do? -> Describe the code and algorithm step by step.
2. What does it do? -> You may skip this part if the experienced behaviour is the same as expected behaviour.
3. What is the question? -> Explain the question "Why this code converge?", i.e. what do you mean by that, and how should an answer look like.

 RomanM 2021-07-28 20:21

Ok!
1. Code find the values of t>sqrt(p) (p - any number. Can be prime or composite), for those mod(t^2,p)<sqrt(p) and do this in a [B]very[/B] unusual way, far away from common approach.
Algorithm is quite simple.

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

So t=ceil(sqrt(b^2-a)). t is [B]some[/B] integer) Let u=t, and go all this again, in cycle.
After few step, the value of b became less than sqrt(p) (or cycle go to some ring)

2. See 3.
3. why the hell does this even work???

 Batalov 2021-07-29 01:22

[QUOTE=RomanM;584239]
3. why the hell does this even work???[/QUOTE]
Well, how do you know that it [I]actually [/I]works? Did you try it on all input values up to some limit and then declare "I tested it for all values up to 10^9 and it converged every time".

Maybe if you did that, then there could have been some discussion?
Before you did that how would you convince people that there is anything worth spending their time or even [I]considering [/I]spending time reading past 1st post?

All you are showing is "I tested this on one number! Look!"
Everyone says: "meh" and moves on to reading something else.

 charybdis 2021-07-29 02:22

Write [$]\left\lceil \sqrt{b^2-a} \right\rceil[/$] as [$]\sqrt{b^2-a}+\epsilon[/$], where [$]\epsilon[/$] is between 0 and 1. Let's see what happens when we square this. We get [$]b^2-a+2\epsilon\sqrt{b^2-a}+\epsilon^2[/$].
We know that [$]b^2-a[/$] is a multiple of p, so the value of b on the next iteration is at most (and turns out to be equal to) [$]2\epsilon\sqrt{b^2-a}+\epsilon^2[/$], which is around [$]2\epsilon b[/$] (until b gets close to sqrt(p), when it will tend to be smaller; for b < sqrt(p) it will be 0). In other words, we multiply b by [$]2\epsilon[/$] to get the new value of b.

If [$]\epsilon[/$] behaved like a uniformly random number between 0 and 1, then we would expect values of b to decrease in the long term (exercise: what is the expected rate of decrease?). From the Taylor expansion we see that [$]\epsilon[/$] is roughly equal to the fractional part of [$]\frac{a}{2b}[/$]. For small b this does behave essentially like a uniformly random number between 0 and 1; for some larger b it is skewed towards the smaller end, but this still means we expect b to fall.

There may be a neater explanation; this is just the first thing I came up with.

 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]
[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 07:31.