December 10th, 2007, 04:54 PM  #1 
Senior Member Joined: Nov 2007 Posts: 633 Thanks: 0  Transparent semiprimes
Good evening, Let us take the number N=1633. 1633=23*71 is semiprime number. Now let us apply the following algorithm ("digit factorizing" or DF). 1. We take the last digit 3 and we compute int(sqrt(3))=1 2. We take the 2 last digits 33 and we compute int(sqrt(33))=5 3. We do the same with 633 we obtain int(sqrt(633))=25 4. The same with 1633 result : int(sqrt(1633))=40 5. Now we add all the values : s=1+5+25+40=71 71 is one of the factors of 1633. Sometimes the number s that we obtain by applying the algo has the gcd with N different than one. Example : N=3*19=57 s= 2+7=9 gcd(57,9)=3 Definition : N is called a transparent semiprime number when we can find its factors by applying the digit factorizing (DF) algorithm. How many semiprimes are transparent between 4 and 10^12? Are the transparent semiprimes random numbers? I need your help thank you. 
December 15th, 2007, 10:04 PM  #2 
Newbie Joined: Dec 2007 Posts: 17 Thanks: 0 
I am really interested in your transparent semi prime number.Has anyone thinked abt it before or u invented it? Can the algorithm be used to break turings code if that is a transparent semi prime? 
December 16th, 2007, 04:05 AM  #3 
Global Moderator Joined: Dec 2006 Posts: 20,823 Thanks: 2159 
I tried this on a handful of 4digit semiprimes without any success. How did you find your example of 1633?

December 16th, 2007, 08:22 AM  #4  
Senior Member Joined: Nov 2007 Posts: 633 Thanks: 0  Quote:
What I do not know it that there are big numbers (more than 200 digits) having that property. Here in my blog you can read about transparent semiprimes (in french) http://tamarouf.hautetfort.com/archive/ ... rents.html There are others ways to find those numbers. My idea is : if we cand find three or four fast ways to check semiprimes that will cover at least 60 per cent of them it will be added as module for factorizing.  
December 16th, 2007, 08:34 AM  #5  
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms 
momo, I can't imagine testing this up to 10^12; that would take a lot of factoring. Here's the list up to 10 million: 15 35 119 253 377 851 989 1633 2759 9047 9869 18673 20227 24139 63893 65693 71051 98093 183643 253217 320233 326699 348301 352139 382387 443747 446987 454837 488857 502561 507427 527707 552781 557827 719843 733049 749699 758293 817477 844871 955099 997523 1374091 1483571 1592803 1593973 1819789 1925113 2030579 2855551 3279557 3296299 3709763 3734827 3752011 3886549 3943463 4052131 4189037 4226267 4414903 4461101 4624337 4727651 5726993 5742593 5917399 5967041 6004511 6057719 6117973 6507559 6696251 6976187 7265849 7298251 7706957 7986101 8051027 8173381 8479469 8675167 9434563 9604921 Quote:
 
December 16th, 2007, 08:39 AM  #6 
Senior Member Joined: Nov 2007 Posts: 633 Thanks: 0 
It seems to me that you have forgotten those with gcd different than one like 57 int(sqrt(7)=2 int(sqrt(57)=7 s=2 + 7 = 9 gcd(57,9)=3. Just read what I said before. 33, 39, 57, 65 and so on are transparent too. You have to compare those numbers to all the odd semiprimes and you will find two out seven. Just imagine if one of the semiprimes of RSA challenge fall on that category. RSA will be in a big trouble. They are others ways to find those transparent numbers. Example by adding int(sqrt(n) to the remain (let us call the sum s) and computing gcd(n,s) like the number 39 int(sqrt(39)=6 remain = 3 s=6+3=9 gcd(39,9)=3 I have found for now 12 ways and I'm trying to eliminate some to have more efficiency. 
December 16th, 2007, 02:46 PM  #7 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms 
In that case your list will be mostly even semiprimes.

December 16th, 2007, 02:55 PM  #8  
Senior Member Joined: Nov 2007 Posts: 633 Thanks: 0  Quote:
What I'm looking for it's a way to check at least 60 per cent of odd semiprime by using a limited number of fast algo. Why I'm telling this? Because RSA could not guess all the possibilities. My suspicion is there is always some hole in any cryptographic system.  
December 16th, 2007, 05:19 PM  #9 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms 
Do you have any reason to believe that your algorithm is more likely to give a nontrivial factor than choosing a random odd number of size ~ sqrt(n) and taking the gcd? As for the RSA numbers:
In general, I'm highly suspicious of any algorithm that applies specifically to the base10 representation of a number. 
December 16th, 2007, 06:07 PM  #10 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms 
There are 18,245 odd semiprimes from 15 to 100,000. Of those 2,274 (12%) have gcd(n, f(n)) > 1 where f(n) is your square root sum function. But 7,500 (41%) have gcd(n, 105) > 1. To get the 60% you want in this range you could use gcd(n, 4849845). Of course these figures will drop off rather quickly. Now here are heuristic figures for comparison. Suppose N = pq is an odd semiprime where p < q < 2p. Then there are about 2sqrt(N) numbers k in (1, N) with kN. Simply picking a number uniformly at random from [1, N] gives a 2/sqrt(N) chance of finding a nontrivial factor of N. Choosing an odd on [sqrt(N)/sqrt(2), sqrt(N)] gives something like a 6.8/sqrt(N) chance of finding the smaller prime factor directly. Your method samples essentially at random on something like [sqrt(N), 1.5sqrt(N)]. p isn't in this range, but q is and 2p might be. No others multiples of p or q are in the range. In the best case, then, this gives a 2/0.5sqrt(N) = 4/sqrt(N) chance of finding a factor, with only half that chance if p is close to the square root. If instead of having the prime factors close together (factor of 2) they are far apart, the best method is to simply choose a small odd number. For example if p^2 ~= q then choosing a random odd from [3, 2 N ^(1/3)] gives a 1/N^(1/3) or better chance of finding p, which is better than the above chances for N > 1000 or so. 

Tags 
semiprimes, transparent 
Search tags for this page 
Click on a term to search for related topics.

Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Sum of digits and odd semiprimes  mobel  Number Theory  10  February 9th, 2014 08:41 AM 
Ellipse: semimajor axis (a) as a function of semiminor (b)  courteous  Algebra  11  November 24th, 2011 01:27 AM 
Factorization of big odd semiprimes  Bogauss  Number Theory  8  February 16th, 2011 08:51 AM 
New sequence containing all the primes + some semiprime  momo  Number Theory  16  February 24th, 2010 05:11 AM 
World Breaking Transparent Math  James  Algebra  6  December 31st, 1969 04:00 PM 