My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
LinkBack Thread Tools Display Modes
December 10th, 2007, 04:54 PM   #1
Senior Member
 
Joined: Nov 2007

Posts: 633
Thanks: 0

Transparent semi-primes

Good evening,

Let us take the number N=1633.
1633=23*71 is semi-prime 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 semi-prime number when we can find its factors by applying the digit factorizing (DF) algorithm.

How many semi-primes are transparent between 4 and 10^12?
Are the transparent semi-primes random numbers?

I need your help thank you.
momo is offline  
 
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?
apratim is offline  
December 16th, 2007, 04:05 AM   #3
Global Moderator
 
Joined: Dec 2006

Posts: 20,823
Thanks: 2159

I tried this on a handful of 4-digit semiprimes without any success. How did you find your example of 1633?
skipjack is online now  
December 16th, 2007, 08:22 AM   #4
Senior Member
 
Joined: Nov 2007

Posts: 633
Thanks: 0

Quote:
Originally Posted by skipjack
I tried this on a handful of 4-digit semiprimes without any success. How did you find your example of 1633?
I tried it for semi-primes less than one million 2 out of seven are transparent.
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 semi-primes (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 semi-primes that will cover at least 60 per cent of them it will be added as module for factorizing.
momo is offline  
December 16th, 2007, 08:34 AM   #5
Global Moderator
 
CRGreathouse's Avatar
 
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:
Originally Posted by skipjack
I tried this on a handful of 4-digit semiprimes without any success.
These numbers are far too rare to be useful as a factoring method.
CRGreathouse is offline  
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 semi-primes and you will find two out seven.

Just imagine if one of the semi-primes 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.
momo is offline  
December 16th, 2007, 02:46 PM   #7
Global Moderator
 
CRGreathouse's Avatar
 
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.
CRGreathouse is offline  
December 16th, 2007, 02:55 PM   #8
Senior Member
 
Joined: Nov 2007

Posts: 633
Thanks: 0

Quote:
Originally Posted by CRGreathouse
In that case your list will be mostly even semiprimes.
Do not count even semi-primes because it is clear that they are divided by 2.
What I'm looking for it's a way to check at least 60 per cent of odd semi-prime 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.
momo is offline  
December 16th, 2007, 05:19 PM   #9
Global Moderator
 
CRGreathouse's Avatar
 
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:
  • The RSA challenge is no longer open, at least according to their page.[/*:m:2bmtny4l]
  • None of RSA-2048, RSA-1536, RSA-1024, RSA-896, RSA-768, or RSA-704 have nontrivial factors found by this algorithm.[/*:m:2bmtny4l]

In general, I'm highly suspicious of any algorithm that applies specifically to the base-10 representation of a number.
CRGreathouse is offline  
December 16th, 2007, 06:07 PM   #10
Global Moderator
 
CRGreathouse's Avatar
 
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 k|N. 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.
CRGreathouse is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

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 semi-primes mobel Number Theory 10 February 9th, 2014 08:41 AM
Ellipse: semi-major axis (a) as a function of semi-minor (b) courteous Algebra 11 November 24th, 2011 01:27 AM
Factorization of big odd semi-primes Bogauss Number Theory 8 February 16th, 2011 08:51 AM
New sequence containing all the primes + some semi-prime momo Number Theory 16 February 24th, 2010 05:11 AM
World Breaking Transparent Math James Algebra 6 December 31st, 1969 04:00 PM





Copyright © 2019 My Math Forum. All rights reserved.