Factorization of Integers without the use of Division or Knowledge of Integer Prime Values

Abstract

This method uses the operations of addition or subtraction in combination with comparison to determine a factor pair from a given odd integer.

Claims

1) The claim of this application is in the use of integer square differences to locate factor pairs and

2) The use of successive odd integer values as a way of forcing a sum to always land on a value that is an integer square.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0011] Key Elements of a Code Implementation:

[0012] An unknown value G is added to a ‘small’ sum which begins with the value of zero.

[0013] The ‘large’ sum is calculated by determining the square root of G and then choosing the smallest integer square larger than that value.

[0014] The new idea here is that of increasing the sum values in a method that guarantees that the new sum value will be an integer square.

[0015] All the odd numbers are used in sequence in either ascending or descending order.

[0016] Because the Pythagorean Theorem guarantees that the difference of integer squares must be representable as a factor pair, the relation ‘large’ sum=G+‘small’ sum will deliver a factor pair when the equation is in balance.

[0017] This description began from the ‘bottom’ where the ‘small’ sum begins at zero.

[0018] It is also possible to start at the top and work down, decrementing the sums at each step instead.

[0019] This makes it possible to partition the collection of terms to be evaluated in many ways.

[0020] The result of this will be to speed up the factoring process and to find a factor pair in a specified amount of time.

[0021] These ideas in combination enable the determination of factor pairs from a given odd integer value. The complexity of addition, subtraction and comparison is recognizably less than what is needed to determine square roots. Division or knowledge of divisors is unnecessary. The example that follows is one of the simplest implementations. It is intended for use in an application such as the 64 bit version of Microsoft Excel. Other implementations in Microsoft C# and the Microsoft Quantum language have been created but are unnecessary here. A boundary value is determined according to the given number provided. If the boundary is reached, no factor pair has been found and the given number is a prime integer.

TABLE-US-00001 PROGRAM CODE: Function findFactor(CellRef As String) As LongLong ′This code uses the 64 bit Excel data type LongLong ′32 bit code uses the Excel data type Long Dim GH As LongLong, GL As LongLong, deltaGH_Sum As LongLong, deltaGL_Sum As LongLong, add2GH As LongLong, add2GL As LongLong, countGH As LongLong, countGL As LongLong, F1 As LongLong Dim F2 As Double Dim Zero As LongLong ′User provides code to deliver the composite number ′and associate it with ′the variable numberToBeFactored′ Dim numberToBeFactored As LongLong numberToBeFactored = 91999 GH = (numberToBeFactored + 1) / 2 GL = (numberToBeFactored − 1) / 2 add2GH = numberToBeFactored − 2 add2GL = numberToBeFactored − 4 countGH = 1 countGL = 1 deltaGH_Sum = numberToBeFactored deltaGL_Sum = numberToBeFactored − 2 F1 = 0 F2 = 0# Zero = 0 While ((add2GH >= Zero) And (add2GL >= Zero)) If (deltaGH_Sum > deltaGL_Sum) Then deltaGL_Sum = deltaGL_Sum + add2GL add2GL = add2GL − 2 countGL = countGL + 1 End If If (deltaGH_Sum < deltaGL_Sum) Then deltaGH_Sum = deltaGH_Sum + add2GH add2GH = add2GH − 2 countGH = countGH + 1 End If If (deltaGH_Sum = deltaGL_Sum) Then F1 = countGL - countGH + 1 F2 = (numberToBeFactored / F1) Rem MsgBox ″F1: ″& F1 & vbNewLine _ rem & ″F2: ″& F2 & vbNewLine _ rem & ″G: ″ & numberToBeFactored GoTo Success End If If ((add2GH = 1) Or (add2GL = 1)) Then GoTo Fail End If Wend Fail: Rem MsgBox ″Non-Trivial Factors not found″ findFactor = 1 Success: If (F1 > 1) Then find Factor = F1 End If ′Console.WriteLine(″″) End Function