My Math Forum  

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

Number Theory Number Theory Math Forum


Thanks Tree5Thanks
Reply
 
LinkBack Thread Tools Display Modes
October 14th, 2015, 04:01 AM   #31
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
Quote:
Originally Posted by mobel View Post
There is no need to factorize n-1.
All you need to know is n-1 odd or even
If it is even then you split in 2. As long as it is even you continue splitting in 2.
What happens if it's no longer even and you haven't found any factors? Do you declare it prime?
CRGreathouse is offline  
 
October 14th, 2015, 04:15 AM   #32
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
Quote:
Originally Posted by mobel View Post
Computing gcd`s does not require factorization at all!
Correct. Even the 'naive' Euclidean algorithm does it pretty quickly, certainly much more quickly than factoring. Further, computing (say)
$$
\gcd\left(2^{(p-1)/2}+1,n\right)
$$
doesn't require working with huge numbers: you can use modular exponentiation to find $2^{(p-1)/2}\pmod n$ and then find the gcd. So for example, with n = 7500234831103067317545753367960619620902953277223, I find $2^{(n-1)/2}\equiv1\pmod n$ and so $\gcd(2^{(p-1)/2}+1,n)=\gcd(2,n)=1.$ If I had to find $2^{(n-1)/2}$ explicitly it wouldn't fit in the universe.

So this part isn't a problem.
CRGreathouse is offline  
October 14th, 2015, 04:45 AM   #33
Banned Camp
 
Joined: Dec 2013

Posts: 1,117
Thanks: 41

Quote:
Originally Posted by CRGreathouse View Post
What happens if it's no longer even and you haven't found any factors? Do you declare it prime?
I have the solution when it`s no longer even and become odd.
First when n-1 stay even k times (for example) do you recognize that many pseudo-prime numbers will be eliminated? yes or no?
Second when n-1 at some stage become odd WE DO NOT NEED to factorize it.
I have the solution but I will keep it for me.
You know why?
Because you did not say that it is ASTRONOMICAL to factorize n-1 when other primality tests USE THE FACTORIZATION OF N-1.
So my conclusion is that you are sabotaging my idea. You are dishonest.
You did not correct Al-Mahed many times.
561 failed my test and you know it you did not correct.
Computing gcd does not require factorization of n-1 you did not correct Al-Mahed until I post my correction.

I`m not going to spend my time correcting each one who did not read my posts. It is a waste of time.
No one talks about the core of my test.
NO ONE.
Only comments are either out of the subject either comments of bad faith like yours.

I`m not playing the victim as you claimed nor Galileo stuff.
Here you see clearly that you are de "MAUVAISE FOI".
Your goal is not to help. No. You goal is to play the teacher.
Did you post any of your works? NOOOOOOOOOOOOOOOOOO
Did you suggest any idea to be discussed? NOOOOOOOOOOOOOO
You are just answering as if you are a teacher. You are a BAD TEACHER because you have no knowledge of mathematics. You are a programmer (not even of high level I know programmers of high level) who claim to be mathematician. You use the computer before using a paper and pen.

Now that I have said what I have to say good luck to your forum.
Try to encourage others to participate. As long as you are dominating the forum the forum will have no future. If you for some reason you stop participating the forum will sink.
mobel is offline  
October 14th, 2015, 06:11 AM   #34
Senior Member
 
Joined: Dec 2007

Posts: 687
Thanks: 47

Quote:
Originally Posted by CRGreathouse View Post
Correct. Even the 'naive' Euclidean algorithm does it pretty quickly, certainly much more quickly than factoring.
Correct if you are reading "factoring" as getting all primes and their powers. If I can get any divisor of a number, which is what is intended here, then this I call "a factor", the same for getting a gcd, so clearly to compute a gcd is to compute a factor and that's what was meant.

Just a matter of terminology: in this sense, to claim that finding gcd's does not involve any factorization is absurd.

If that suits it better, instead of saying "you need to factorize decreasing $2^x$", say "you need to find the gcd of decreasing $2^x$", what anyway seems worse than computing $n$ against a list of previously given primes smaller than $\sqrt{n}$.
al-mahed is offline  
October 14th, 2015, 06:42 AM   #35
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
Quote:
Originally Posted by al-mahed View Post
Just a matter of terminology: in this sense, to claim that finding gcd's does not involve any factorization is absurd.
I disagree, but perhaps our disagreement is merely one of terminology. Let me put it this way. Given a million-digit number, I can find the gcd of that number with RSA-2048 in about 2 milliseconds, even though factoring RSA-2048 is not possible with current technology (not even with millions of dollars' worth of computer time).

Last edited by CRGreathouse; October 14th, 2015 at 06:53 AM.
CRGreathouse is offline  
October 14th, 2015, 09:34 AM   #36
Senior Member
 
Joined: Dec 2007

Posts: 687
Thanks: 47

Yes, I guess it is just a matter of terminology, maybe mine was misleading, but I meant to say that usually, in worst (and likely most) case scenarios, transferring the problem from $n$ to $2^\frac{n-1}{2^y}$ powers that way increases wildly the complexity, but in general this is obviously not very precise because "given some method to calculate the gcd" is very vague. So the comment was addressing that particular method against working with $n$ by any other known means.

But let me now just pose a question taking your example: We have such a million-digit number, say it is $n$. Now $2^\frac{n-1}{2^y}\pm 1$ for the first steps of the intended method, i.e., for small $y$, will give us approximately floor(n*log(2)/log(10)) + 1 for $n$ being the million-digit number, which I cannot conceive how many digits such power of 2 would have; call it "unspoken-digit number". Now the question: RSA2048 can find the gcd of two given million-digit numbers in 2 milliseconds as I understood it, but is it the case if the million-digit number is tested against the "unspoken-digit number"?
al-mahed is offline  
October 14th, 2015, 09:43 AM   #37
Banned Camp
 
Joined: Dec 2013

Posts: 1,117
Thanks: 41

Quote:
Originally Posted by al-mahed View Post
Correct if you are reading "factoring" as getting all primes and their powers. If I can get any divisor of a number, which is what is intended here, then this I call "a factor", the same for getting a gcd, so clearly to compute a gcd is to compute a factor and that's what was meant.

Just a matter of terminology: in this sense, to claim that finding gcd's does not involve any factorization is absurd.

If that suits it better, instead of saying "you need to factorize decreasing $2^x$", say "you need to find the gcd of decreasing $2^x$", what anyway seems worse than computing $n$ against a list of previously given primes smaller than $\sqrt{n}$.
That is not what you said sir.
You are just trying to escape by getting into terminology problem.
You said that you need the factorization to compute the gcd and you add that it will be very complicated to do it.
I quote you :
"so now you are let to factorize not n but a series of astronomically larger power of 2"

Why such dishonesty?
To save you ego?

Your comments are wrong for 2 reasons :
- you did not read carefully what was written
- your goal was just to sabotage my idea.
I`m not rude! I`m honest and I dislike people playing the teachers without having enough knowledge to do it.

I`m not teacher (I was tens of years ago).
I`m not a programmer.
I do not know all the mathematical technics in detail.
But I can understand a proof. I can understand what tool could be used to solve some problem. I can solve lot of problems by taking new approaches and imaginative ways.
After all of that I`m honest not tricky guy.
I apologize when I say something wrong.
I recognize my errors each time I make a mistake.
When I was on "lycee" (college?) I was the first one in mathematics out of 3500 students. I had never be noted less than 20 out of 20.
I`m old now and I do not have enough energy to focus on calculations.
I`m not mad but I will never ever be kind even with my brothers when they act or say something wrong.
mobel is offline  
October 14th, 2015, 10:03 AM   #38
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
Quote:
Originally Posted by al-mahed View Post
RSA2048 can find the gcd of two given million-digit numbers in 2 milliseconds as I understood it
A small correction here: RSA-2048 is just a number, one with 617 decimal digits. I picked it only because it's known to be hard to factor.

Quote:
Originally Posted by al-mahed View Post
But let me now just pose a question taking your example: We have such a million-digit number, say it is $n$. Now $2^\frac{n-1}{2^y}\pm 1$ for the first steps of the intended method, i.e., for small $y$, will give us approximately floor(n*log(2)/log(10)) + 1 for $n$ being the million-digit number, which I cannot conceive how many digits such power of 2 would have; call it "unspoken-digit number". Now the question: RSA2048 can find the gcd of two given million-digit numbers in 2 milliseconds as I understood it, but is it the case if the million-digit number is tested against the "unspoken-digit number"?
This is a good question -- it shows that you've been paying attention. Yes, this is quite a bit harder than finding the gcd of the million-digit number with another million-digit number (or even easier, the gcd of the million-digit number with RSA-2048).

Almost all of your time is spent on modular exponentiation, not on the gcd itself. The exponentiation will take about 3.3 million squarings and a few million multiplications, all of which will be on million-digit numbers.

Here are some order of magnitude estimates on the time needed:
  • Find gcd of a 617-digit number with a million-digit number: 2 ms
  • Multiply two million-digit numbers: 20 ms
  • Find gcd of two million-digit numbers: 0.5 seconds
  • Compute a modular exponentiation with a million-digit modulus and exponent: 1 week
Thanks from al-mahed
CRGreathouse is offline  
October 15th, 2015, 01:13 AM   #39
Member
 
Joined: Oct 2013

Posts: 60
Thanks: 6

Quote:
Originally Posted by CRGreathouse View Post
I disagree, but perhaps our disagreement is merely one of terminology. Let me put it this way. Given a million-digit number, I can find the gcd of that number with RSA-2048 in about 2 milliseconds, even though factoring RSA-2048 is not possible with current technology (not even with millions of dollars' worth of computer time).
Correct. The euclidian gcd algorithm is one of the best developed ever.

Here's an amazing example:
Someday a spy gives us a 'secret' number A=m*p:
Code:
23628542307141981241869560860159046098340361824025619659548500025775322220096370349965444223173235616148122970792396418281481383022650981891922027692667343340689504264580618823412688321464938202931103160890890100964641014541824824305460266838847531046185922338984604982241517890753508023878559165753236302547176182719498313289212514733359728962494853073355084849877786361675646187011443947062748479632148325865522285256844949541254811427385125732834560592234448784454051056397689
Trying to factorize the number will take months and years of intense computations.
Small chance to reveal the message m within a lifetime.

Then someday another spy gives us number B=m*q:
Code:
73388221100734851384386742176828049006448498778457457535953122929017416833624142727586441442982113060083729476893370704651207503752095428362302320772755519312854759908951743677154937975118174637116716231763272528182432263522485096825521224250965224397381191955358946383972337439987020677622852371840582614159070609330095850441960341997818010873921972711774600685806035463965298546632731399313076922710696707363120769649370657933907141217818113129631703776441583847943639113905937
Again unable for a factorisation of B, we soon realize that gcd(A,B) will reveal m immediately(<10ms). Math is fun.

This was a rather uncommon example in cryptography but amusing I hope.
m is the secret project i'm working on at the moment.

But seriously, also pointing to mobel, I wish we can someday build a workshop here on interesting topics.
A place where we discuss on-theme and peacefully, developing something really new.
Every mathematician has his ideas. Constructive criticism is a necessity,but also politeness and respect for each other.
I see this forum as a think-tank where every member can contribute.

Last edited by Martin Hopf; October 15th, 2015 at 01:33 AM.
Martin Hopf is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
breaking, fermat, news, pseudoprimes



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
Fermat primes fafa Number Theory 4 July 10th, 2013 11:25 AM
Problems driving me crazy.(Primes,Fermat,Euler) usermind Number Theory 1 October 5th, 2010 09:30 AM
Pseudo-finite fields Mathworm Abstract Algebra 1 March 5th, 2009 02:20 PM
Pseudo-Diophantine Nuisance reddmann Number Theory 2 August 30th, 2007 08:03 AM





Copyright © 2019 My Math Forum. All rights reserved.