mersenneforum.org How to quick find x, x^4 mod N
 Register FAQ Search Today's Posts Mark Forums Read

 2021-07-12, 17:12 #12 RomanM   Jun 2021 41 Posts The sieve v 1.0 Ugly, non-elegant, Tea Time style. This sieve is memory hungry and in spite of being exponentially fast on the really large upper bound (if you have plenty of memory)), and can be greatly improved. It's using the most obvious way to sieve, there is at least two more. Code: \p300 {p=233108530344407544527637656910680524145619812480305449042948611968495918245135782867888369318577116418213919268572658314913060672626911354027609793166341626693946596196427744273886601876896313468704059066746903123910748277606548649151920812699309766587514735456594993207; c=ceil(sqrt(p)); v=vector(2000000); S=vector(2000000); for(n=1,200000, \\200000-upper bound of sieve, can be large) u=c+n; b=lift(Mod(u^2,p)); a=lift(Mod(b^2,p)); t=ceil((b^2-a)^(1/2)); v[n]=t;); v=vecsort(v,,8); j=1; for(k=1,300, \\dummy loop vecmax(v,&z); print(z);\\some digit on the screen for(n=1,z, u=v[n]; b=lift(Mod(u^2,p)); a=lift(Mod(b^2,p)); if(bc, t=ceil((b^2-a)^(1/2)); v[n]=t; ); ); v=vecsort(v,,8); \\the "sieve" hiding here ); S=vecsort(S,,8); print(S); }
2021-07-14, 05:39   #13
RomanM

Jun 2021

1010012 Posts

Hello. ~10x speedup, just feeding the "sieve" by other set of initial values. And you understand, that output subsqrt residuals means nothing but the way how we get them?
Attached Files
 1.txt (946 Bytes, 45 views)

 Similar Threads Thread Thread Starter Forum Replies Last Post henryzz Factoring 18 2010-09-26 00:55 XYYXF Math 2 2007-12-08 12:31 hallstei Factoring 7 2007-05-01 12:51 R.D. Silverman NFSNET Discussion 11 2006-07-20 17:04 Crook Math 3 2005-10-26 21:29

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

Thu Dec 2 04:42:00 UTC 2021 up 131 days, 23:11, 0 users, load averages: 1.19, 1.17, 1.18