Brilliant numbers

alpertron · 2006-04-22, 01:20

For those who like to use SNFS for factorization, I have a challenge.

In http://www.alpertron.com.ar/BRILLIANT.HTM I collected so-called "brilliant numbers". They have the same number of digits when factored (like RSA). The problem here is to find the largest brilliant number with odd number of digits and the smallest brilliant number with even number of digits.

For example, in order to discover that 10¹¹³ - 91227 is the largest 113-digit brilliant number, Sander Hoogendoorn had to perform 350 SNFS factorizations of this size.

Citrix · 2006-04-22, 03:50

I suggest you sieve numbers using newpgen. If the number has small factors then it will not be part of your list. Then eliminate all prime numbers. Then do a few curves of ECM, eliminating more candidates and then continue to more drastic methods.

As for the sieve bounds if

10^n-x and 10^n+x are both prime then the Brilliant number of 2n digits must be between 10^2n and 10^2n-x^2.

Finding the smallest number with x digits is more challenging, since it is difficult to describe the bounds.

Citrix

alpertron · 2006-04-22, 13:01

Almost all numbers are discarded using ECM. Notice that he had to perform SNFS on only 350/91227 = 0.38% of the possible numbers.

smh · 2006-04-23, 10:11

Quote:

Originally Posted by alpertron

Almost all numbers are discarded using ECM. Notice that he had to perform SNFS on only 350/91227 = 0.38% of the possible numbers.

Actually, most numbers were discared using trail factoring.

I don't think newpgen can sieve these kind of numbers.
And the version of cpapsieve that i have can only do the + side, but trail factoring with pfgw will remove most candidates.

Running a few ECM curves with low bounds will quickly remove the majority of the remaining numbers.

I ran quite a bit more ecm. Only 6 of the 350 tested numbers turned out to have a factor of 28 or 29 digits.

grandpascorpion · 2006-04-24, 01:35

Dario,

I'll give 114 a try.

smh · 2006-04-24, 07:15

I think 114 is being done by David Cleaver.

I'm doing 116 atm

axn · 2006-04-24, 18:34

Does any one have any sieving program that can handle these forms -- preferably one that can do +/- simultaneously?

I could write one, but it would be limited to p < 2^32

alpertron · 2006-04-24, 18:53

Quote:

Originally Posted by axn1

Does any one have any sieving program that can handle these forms -- preferably one that can do +/- simultaneously?

I could write one, but it would be limited to p < 2^32

Please notice that for even number of digit only the "+" part is needed and for odd number of digits only the "-" part is needed. This is because the other two cases are trivial.

Citrix · 2006-04-24, 18:57

could I reserve 121 and 120

axn · 2006-04-24, 19:02

Quote:

Originally Posted by alpertron

Please notice that for even number of digit only the "+" part is needed and for odd number of digits only the "-" part is needed. This is because the other two cases are trivial.

Yes. But taking the example of 10^113. 10^113-n is 113 digits and 10^113+n = 114 digits. So n odd and n+1 even can both be simultaneously sieved by 10^n+/-. In fact, I realised this by looking at _your_ tables

So it makes sense to attack them together.

alpertron · 2006-04-24, 19:13

You're right. That's the problem when one writes in "automatic mode" without thinking a bit.

2006-04-22, 01:20	#1
alpertron Aug 2002 Buenos Aires, Argentina 2526₈ Posts	Brilliant numbers For those who like to use SNFS for factorization, I have a challenge. In http://www.alpertron.com.ar/BRILLIANT.HTM I collected so-called "brilliant numbers". They have the same number of digits when factored (like RSA). The problem here is to find the largest brilliant number with odd number of digits and the smallest brilliant number with even number of digits. For example, in order to discover that 10¹¹³ - 91227 is the largest 113-digit brilliant number, Sander Hoogendoorn had to perform 350 SNFS factorizations of this size.

2006-04-24, 18:57	#9
Citrix Jun 2003 2×7×113 Posts	could I reserve 121 and 120 Last fiddled with by Citrix on 2006-04-24 at 18:58

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
3-brilliant	fivemack	Factoring	4	2017-11-02 22:36
Six-brilliant numbers	fivemack	Miscellaneous Math	13	2012-05-03 23:56
6 digit numbers and the mersenne numbers	henryzz	Math	2	2008-04-29 02:05
10^119+x brilliant number	Citrix	Prime Sierpinski Project	12	2006-05-19 22:21
LLT numbers, linkd with Mersenne and Fermat numbers	T.Rex	Math	4	2005-05-07 08:25

2006-04-22, 03:50	#2
Citrix Jun 2003 11000101110₂ Posts	I suggest you sieve numbers using newpgen. If the number has small factors then it will not be part of your list. Then eliminate all prime numbers. Then do a few curves of ECM, eliminating more candidates and then continue to more drastic methods. As for the sieve bounds if 10^n-x and 10^n+x are both prime then the Brilliant number of 2n digits must be between 10^2n and 10^2n-x^2. Finding the smallest number with x digits is more challenging, since it is difficult to describe the bounds. Citrix

2006-04-22, 13:01	#3
alpertron Aug 2002 Buenos Aires, Argentina 2·683 Posts	Almost all numbers are discarded using ECM. Notice that he had to perform SNFS on only 350/91227 = 0.38% of the possible numbers.

2006-04-24, 01:35	#5
grandpascorpion Jan 2005 Transdniestr 503 Posts	Dario, I'll give 114 a try.

2006-04-24, 07:15	#6
smh "Sander" Oct 2002 52.345322,5.52471 29·41 Posts	I think 114 is being done by David Cleaver. I'm doing 116 atm

2006-04-24, 18:34	#7
axn Jun 2003 5,087 Posts	Does any one have any sieving program that can handle these forms -- preferably one that can do +/- simultaneously? I could write one, but it would be limited to p < 2^32

2006-04-24, 19:13	#11
alpertron Aug 2002 Buenos Aires, Argentina 10101010110₂ Posts	You're right. That's the problem when one writes in "automatic mode" without thinking a bit.