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
January 30th, 2018, 06:03 AM   #1
Member
 
Joined: Jan 2015
From: italy

Posts: 39
Thanks: 1

Semi-prime factorization conjecture

Let N be a semiprimo then

N=a^2-b^2 will have two solutions

a1=(N+1)/2 and b1=(N-1)/2

a2=? b2=? bruteforce on b2 starting from 0

A+B=a1 , A-B=a2 , C+D=b1 ,C-D=b2

gcd(A,C)=p_a
gcd(B,D)=p_b
p=(p_a^2-p_b^2)
gcd(A,D)=q_a
gcd(B,C)=q_b
q=(q_b^2-q_a^2)


Example

15=a^2-b^2

a=4 b=1
a=8 b=7

A+B=8 , A-B=4 , C+D=7 , C-D=1
A=6 ,B=2 ,C=4 ,D=3

gcd(A,C)=2
gcd(B,D)=1
p=(2^2-1^2)=3
gcd(A,D)=3
gcd(B,C)=2
q=(3^2-2^2)=5

What do you think about it?
gerva is offline  
 
January 30th, 2018, 08:02 PM   #2
SDK
Senior Member
 
Joined: Sep 2016
From: USA

Posts: 413
Thanks: 227

Math Focus: Dynamical systems, analytic function theory, numerics
This is known as the quadratic sieve factoring algorithm. Its slightly souped up big brother (the number field sieve) is the currently the fastest known factoring algorithm for integers which aren't the product of "a lot" of smaller factors. In this case, the ellliptic curve factoring algorithm is extremely fast which leads to the common strategy.

1. Given a number to be factored, use EC factoring to split off small divisors until the remaining product is the product of only a few large factors. It is easy to check primality so you can tell when this happens because EC stops giving you results but primality tests still fail.

2. Switch to number field sieve (or quadratic sieve) and try to split off larger factors.
SDK is offline  
January 31st, 2018, 08:21 AM   #3
Member
 
Joined: Jan 2015
From: italy

Posts: 39
Thanks: 1

thank you
gerva is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
conjecture, factorization, semiprime



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Factorization of odd semi prime is over! mobel Number Theory 32 August 21st, 2016 11:32 AM
Semi-prime factorization method? cm318 Number Theory 20 April 4th, 2015 04:17 PM
Conjecture about odd semi-prime numbers mobel Number Theory 9 July 1st, 2014 09:58 AM
Factorization of large semi-prime numbers:a partial solution Bogauss Number Theory 58 November 28th, 2011 11:19 AM
Semi-prime numbers and factorization momo Number Theory 19 June 23rd, 2008 09:18 AM





Copyright © 2018 My Math Forum. All rights reserved.