mersenneforum.org  

Go Back   mersenneforum.org > Search Forums

Showing results 1 to 25 of 82
Search took 0.01 seconds.
Search: Posts Made By: mgb
Forum: Factoring 2021-03-28, 13:58
Replies: 9
Views: 2,674
Posted By mgb
It seems you have to calculate these x values one...

It seems you have to calculate these x values one by one as there is no known formula for 'looking ahead' with such a random algorithm. This might interest you...
Forum: Other Mathematical Topics 2021-03-28, 12:18
Replies: 3
Views: 3,949
Posted By mgb
Yes. It follows then that the roots are u =...

Yes. It follows then that the roots are

u = 2-1(a + a-1r)(mod p)

v = 2-1(a - a-1r)(mod p)

for u^2 - v^2 = q1 - q2 = r (mod p)
Forum: Miscellaneous Math 2020-06-18, 11:03
Replies: 4
Views: 1,743
Posted By mgb
Sorry about that. Here you go- The function...

Sorry about that. Here you go-

The function ai+1 = (ai^2 + 1) (mod n) is typical of the kind used in Pollard's Rho Method. The sequence is divided into two parts. The 'tail' and the 'cycle'. But...
Forum: Miscellaneous Math 2020-06-17, 21:11
Replies: 4
Views: 1,743
Posted By mgb
Some Notes on Pollard's Rho

I have been examining the output from Pollard's method for different seeds and an interesting picture has emerged which you might have use for. Comments welcome as always.
...
Forum: Lounge 2020-06-12, 21:54
Replies: 10
Views: 1,859
Posted By mgb
Our science teacher once showed us how phosphorus...

Our science teacher once showed us how phosphorus fizzes in water. Then we got a new science teacher and we asked him to do the phosphorus trick for us. He put in WAY too much and it exploded with...
Forum: Lounge 2020-06-12, 21:28
Replies: 10
Views: 1,859
Posted By mgb
Talking LOL Great analogy.

LOL Great analogy.
Forum: Lounge 2020-06-12, 21:23
Replies: 10
Views: 1,859
Posted By mgb
You caught all the essential points. When I read...

You caught all the essential points. When I read it first I thought this guy was really on to something but then I thought (p + q)/N? Where did he get p and q? He's pulling rabbits out of hats here....
Forum: Lounge 2020-06-12, 19:04
Replies: 10
Views: 1,859
Posted By mgb
Interesting idea on factoring

This is interesting but how does he find Nf(N)?

https://mae.ufl.edu/~uhk/QUICK-SEMI-PRIME-FACTORING.pdf
Forum: Miscellaneous Math 2020-05-20, 20:33
Replies: 31
Views: 13,373
Posted By mgb
See 'Safe Primes' and Sophie Germain primes:...

See 'Safe Primes' and Sophie Germain primes: https://en.wikipedia.org/wiki/Safe_prime
Forum: Other Mathematical Topics 2020-02-02, 20:24
Replies: 3
Views: 3,949
Posted By mgb
Yes, I noticed that it works for odd sums as...

Yes, I noticed that it works for odd sums as well.



Yes, this would be equivalent to writing v = (a - a-1c)/2 as v = (a - a-1R)/2 giving a distance of R between q1 and q2

Many thanks for...
Forum: Other Mathematical Topics 2020-02-01, 18:44
Replies: 3
Views: 3,949
Posted By mgb
Creating Consecutive Quadratic Residues

While working on another problem I stumbled across this if anyone has a use for it.

To create all consecutive quadratic residues modulo p, p an odd prime.

For all a < p find a-1(mod p)

If (a...
Forum: Computer Science & Computational Number Theory 2019-12-23, 22:21
Replies: 28
Views: 9,394
Posted By mgb
gcd([sqrt(n)]^2 - t^2, n) for t = 1, 2, 3,... is...

gcd([sqrt(n)]^2 - t^2, n) for t = 1, 2, 3,... is faster than Fermat's.

[sqrt(n)] = t (mod p)
Forum: Computer Science & Computational Number Theory 2019-10-26, 19:21
Replies: 2
Views: 3,323
Posted By mgb
Yes but at step 2 the task is reduced to a...

Yes but at step 2 the task is reduced to a smaller pair of numbers, to which the extended Euclidean algorithm can be applied. This is an immediate saving in processor time. Step 2 = Find r -1 mod a...
Forum: Computer Science & Computational Number Theory 2019-10-25, 19:48
Replies: 2
Views: 3,323
Posted By mgb
Calculating inverses quickly.

Do you think this would be faster than the extended Euclidean Algorithm for finding inverses?

For a given a find a-1 (mod m)

1. Let m = r mod a
2. Find r -1 mod a
3. Let x = a - r -1 (ie, x =...
Forum: Computer Science & Computational Number Theory 2019-08-05, 20:02
Replies: 45
Views: 13,436
Posted By mgb
Yes, it is hard to see how Brent's ideas can...

Yes, it is hard to see how Brent's ideas can apply. At present I can't see how I can find a way to make it leap forward, ie shorten the cycle. I'll work some more on it as I understand it better now...
Forum: Computer Science & Computational Number Theory 2019-08-04, 10:26
Replies: 45
Views: 13,436
Posted By mgb
Many thanks for this. I had been looking for...

Many thanks for this. I had been looking for something similar.
I have found, with this version, that there is no lead in (no tail). The cycle begins at the start. I can see this because if a factor...
Forum: Computer Science & Computational Number Theory 2019-08-03, 16:18
Replies: 45
Views: 13,436
Posted By mgb
Seemingly all this is quite general and...

Seemingly all this is quite general and independent of z2

That is, if we choose any R in the period [1, n - 1] and let Q = n - R then Q = -R (mod n) and therefore mod p and mod q

That is, if R...
Forum: Computer Science & Computational Number Theory 2019-07-21, 21:10
Replies: 45
Views: 13,436
Posted By mgb
Yes I do but I'm not too worried until I can get...

Yes I do but I'm not too worried until I can get it up to speed. Since m = p + z, m2 = z2 mod p and I'm trying to find a way to split z2 off m2. I thought using rho might do this but it just keeps...
Forum: PARI/GP 2019-07-21, 20:47
Replies: 0
Views: 2,640
Posted By mgb
Pari link

Don't know if this Pari documentation has been posted but it is very extensive-

https://buildmedia.readthedocs.org/media/pdf/cypari2/latest/cypari2.pdf
Forum: Computer Science & Computational Number Theory 2019-07-21, 20:28
Replies: 45
Views: 13,436
Posted By mgb
Thanks, but how do I 'backtrack'? Nor sure what...

Thanks, but how do I 'backtrack'? Nor sure what you mean.
Forum: Computer Science & Computational Number Theory 2019-07-21, 19:27
Replies: 45
Views: 13,436
Posted By mgb
Well well...I finally got it to go as fast as the...

Well well...I finally got it to go as fast as the traditional rho. Here is the code.

r = n%m;
R = r;
Q = r;
for(i = 1, Lim,
R = (R^2 + r)%n;
R = (R^2 + r)%n;
Q = (Q^2 + r)%n;
...
Forum: Computer Science & Computational Number Theory 2019-07-21, 13:26
Replies: 45
Views: 13,436
Posted By mgb
You are quite right. There doesn't seem to be a...

You are quite right. There doesn't seem to be a difference. I thought the different ways of writing z2 would make a difference...
Forum: Computer Science & Computational Number Theory 2019-07-21, 10:25
Replies: 45
Views: 13,436
Posted By mgb
That is, for some c and d I want (cp - zs) - (dp...

That is, for some c and d I want (cp - zs) - (dp - zs) = kp for some k. The idea is to get a match at zs

Alternatively (cp - hz2) - (dp - hz2)
Forum: Computer Science & Computational Number Theory 2019-07-21, 10:09
Replies: 45
Views: 13,436
Posted By mgb
Yes, but things work differently when you reduce...

Yes, but things work differently when you reduce mod n. This is what I'm trying to exploit.
Forum: Computer Science & Computational Number Theory 2019-07-21, 09:55
Replies: 45
Views: 13,436
Posted By mgb
Thanks again for that. The -z2 is mod p so (p -...

Thanks again for that. The -z2 is mod p so (p - z2)2
is p2 -2pz2 + z4 whereas (z2)2 is z4
Showing results 1 to 25 of 82

 
All times are UTC. The time now is 08:54.

Thu May 6 08:54:28 UTC 2021 up 28 days, 3:35, 0 users, load averages: 1.42, 1.52, 1.55

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

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.