mersenneforum.org  

Go Back   mersenneforum.org > Search Forums

Showing results 1 to 22 of 22
Search took 0.01 seconds.
Search: Posts Made By: mgb
Forum: Computer Science & Computational Number Theory 2019-08-05, 20:02
Replies: 45
Views: 17,242
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: 17,242
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: 17,242
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: 17,242
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: Computer Science & Computational Number Theory 2019-07-21, 20:28
Replies: 45
Views: 17,242
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: 17,242
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: 17,242
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: 17,242
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: 17,242
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: 17,242
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
Forum: Computer Science & Computational Number Theory 2019-07-20, 10:21
Replies: 45
Views: 17,242
Posted By mgb
(4242421 - 1) factors as [ 2 2] [ 3 2] ...

(4242421 - 1) factors as

[ 2 2]

[ 3 2]

[ 5 1]

[ 7 2]
Forum: Computer Science & Computational Number Theory 2019-07-19, 21:52
Replies: 45
Views: 17,242
Posted By mgb
I take it that 'Ending index' is equivalent to...

I take it that 'Ending index' is equivalent to the number of loop iterations in mine? If that is the case mine seems to be faster in almost all instances.

p 3228341 q 4941967.....140 iterations
p...
Forum: Computer Science & Computational Number Theory 2019-07-19, 18:25
Replies: 45
Views: 17,242
Posted By mgb
Yes, it is necessary to make two copies, n and...

Yes, it is necessary to make two copies, n and n*32. Work on n*32 but do gcd() on n.
Forum: Computer Science & Computational Number Theory 2019-07-18, 21:51
Replies: 45
Views: 17,242
Posted By mgb
Thanks. I'll keep that in mind if I can get this...

Thanks. I'll keep that in mind if I can get this thing up to speed...
Forum: Computer Science & Computational Number Theory 2019-07-18, 21:11
Replies: 45
Views: 17,242
Posted By mgb
Many thanks for doing that. I tried m2 as a...

Many thanks for doing that. I tried m2 as a constant but it changed nothing. One of my ideas was that if cp < m < (c + 1)p there will be many multiples of p in m if c is large and therefore many z...
Forum: Computer Science & Computational Number Theory 2019-07-18, 13:48
Replies: 45
Views: 17,242
Posted By mgb
Thanks for pointing that out. I just threw it in...

Thanks for pointing that out. I just threw it in there while I was doing some quick testing and forgot to change it. At any rate, randomprime() is set up to keep away from nearly squares (small z...
Forum: Computer Science & Computational Number Theory 2019-07-18, 02:31
Replies: 45
Views: 17,242
Posted By mgb
Yes, that is what my results seem to show. Since...

Yes, that is what my results seem to show. Since we are dealing with cp + z^2 and dp - z^2 I thought I could get Rho to cancel the +z^2 and - z^2 leaving a multiple of p but what seems to be...
Forum: Computer Science & Computational Number Theory 2019-07-18, 02:19
Replies: 45
Views: 17,242
Posted By mgb
Have you tested any of the other examples?: ...

Have you tested any of the other examples?:

p 3228341 q 4941967 n 15954354686747 factored at 140 iterations
p 2001049 q 5225501 n 10456483550549 factored at 644 iterations
p 2462041 q 5294981 n...
Forum: Computer Science & Computational Number Theory 2019-07-18, 02:06
Replies: 45
Views: 17,242
Posted By mgb
No, but it factors some Mersenne numbers quickly...

No, but it factors some Mersenne numbers quickly because they have small factors. I have noticed this algorithm depends on p-1 or q-1 having more than three or four factors. If they are safe primes...
Forum: Computer Science & Computational Number Theory 2019-07-17, 20:09
Replies: 45
Views: 17,242
Posted By mgb
p 34094494829 q 15154262241479 n...

p 34094494829 q 15154262241479 n 516676915629415714812091 in 53065360 iterations
Forum: Computer Science & Computational Number Theory 2019-07-17, 17:23
Replies: 45
Views: 17,242
Posted By mgb
Faster for 3 primes. Generally speaking,...

Faster for 3 primes. Generally speaking, semiprimes are hardest.


So far I only tested up to 12 digits or so but I'll try bigger ones soon.



Didn't go near them yet but I'll get back to you.
Forum: Computer Science & Computational Number Theory 2019-07-16, 16:53
Replies: 45
Views: 17,242
Posted By mgb
Factoring semiprimes with restricted Rho method

This algorithm uses a very simplified version of Pollard's Rho method on a well defined set of residues. The idea is that if the Rho function is restricted it can only produce multiples of z2...
Showing results 1 to 22 of 22

 
All times are UTC. The time now is 04:00.


Sun Jan 23 04:00:44 UTC 2022 up 183 days, 22:29, 0 users, load averages: 1.11, 1.04, 1.10

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔