mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Msieve

Reply
 
Thread Tools
Old 2009-12-07, 22:00   #1
jrk
 
jrk's Avatar
 
May 2008

3·5·73 Posts
Default fix integer overflow with deg 4 in sieve_lattice()

In stage1_sieve.c:
Code:
/* structures for storing arithmetic progressions. Rational
   leading coeffs of NFS polynomials are assumed to be the 
   product of two groups of factors p, each of size at most 32
   bits (32 bits is enough for 512-bit factorizations), and 
   candidates must satisfy a condition modulo p^2 */

#define MAX_P ((uint64)(-1))
The comment is wrong, since now degree>=5 can use p up to 64 bits.

But, for degree==4, max p is still 32 bits.

Code:
		if (degree == 4) {
			CUDA_TRY(cuModuleGetGlobal(&L.gpu_p_array, 
					NULL, gpu_module64, "pbatch"))
			done = sieve_lattice_gpu_deg4_64(obj, &L,
				&sieve_small, &sieve_large,
				(uint32)small_p_min, 
				(uint32)small_p_max,
				(uint32)large_p_min, 
				(uint32)large_p_max,
				gpu_info, gpu_kernel64);
		}
Here on degree==4, the factor p is assumed 32 bits but is bounded by MAX_P in sieve_lattice(), leading to a potential overflow and incorrect bounds being used.

The attached patch does a simple fix for this.
Attached Files
File Type: txt msieve-gpu-fix-deg4-overflow.patch.txt (1.8 KB, 113 views)
jrk is offline   Reply With Quote
Old 2009-12-07, 22:01   #2
jrk
 
jrk's Avatar
 
May 2008

3·5·73 Posts
Default

Forgot to mention, this is about msieve-GPU only.
jrk is offline   Reply With Quote
Old 2009-12-07, 23:03   #3
jrk
 
jrk's Avatar
 
May 2008

3×5×73 Posts
Default

Maybe it would be better to instead have different MAX_P defined for the different degrees. (uint32)(-1) for degree==4 and (uint64)(-1) for larger degrees.
jrk is offline   Reply With Quote
Old 2009-12-07, 23:19   #4
jrk
 
jrk's Avatar
 
May 2008

3·5·73 Posts
Default

Quote:
Originally Posted by jrk View Post
Maybe it would be better to instead have different MAX_P defined for the different degrees. (uint32)(-1) for degree==4 and (uint64)(-1) for larger degrees.
I like this patch better than the earlier one. See attached.
Attached Files
File Type: txt msieve-gpu-fix-deg4-overflow.patch.txt (2.5 KB, 103 views)
jrk is offline   Reply With Quote
Old 2009-12-11, 15:44   #5
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

353710 Posts
Default

Quote:
Originally Posted by jrk View Post
I like this patch better than the earlier one. See attached.
Thanks, this is an inconsistency that I missed. Your changes will be in SVN soon (I'm merging the GPU branch into mainline)
jasonp is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
k*b^n+/-c where b is an integer greater than 2 and c is an integer from 1 to b-1 jasong Miscellaneous Math 5 2016-04-24 03:40
The techniques to guard buffers against overflow SarK0Y Programming 0 2014-10-23 21:20
ubasic: overflow? Andi47 Programming 7 2009-02-27 00:20
Always an integer. mfgoode Puzzles 18 2007-07-13 18:03
Integer FFT nevarcds Math 4 2004-07-28 19:14

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

Sun Apr 18 06:08:07 UTC 2021 up 10 days, 48 mins, 0 users, load averages: 1.94, 2.26, 1.89

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.