ESP

Usage of Blockly in integer factorization calculator

  1. Alpertron
  2. Videos of Integer factorization calculator
  3. Blockly

by Dario Alejandro Alpern

Transcription

Hello everybody. Today I will show you the first part of the tutorial of the integer factorization calculator.

To factor a number, you will enter a number and then press the Factor button. If you are using the keyboard, you can press the keys Control and Enter at the same time.

The calculator shows the product of prime factors and related information, such as the number and sum of divisors.

The Euler's totient is the quantity of values coprime to the number given by the user.

Mobius is a number theory function whose value is zero if there are repeated prime factors. Otherwise, the value is 1 if the number of prime factors is even and -1 if it is odd. In our case there are 3 different prime factors, so Mobius equals -1.

The calculator also decomposes the number as a sum of up to 4 squares. In our example, 105 equals 8 squared plus 6 squared plus 2 squared plus 1 squared.

You can view all 8 divisors of 105 by pressing the button Show divisors.

If you only need to check whether the number is prime or not, you can press the Prime button. This uses a probable prime method named BPSW. If the number is less than 2 to the 64 (a 20-digit number), BPSW is always right. For numbers greater than 2 to the 64, if it says that it is not prime, we can be sure that it is not. Otherwise, there is no demonstration that the number is prime. But notice that no one found a counterexample up to this date.

You can enter several lines of numbers, or expressions. When pressing one of the three buttons, the calculator will only evaluate the expressions, show if they are prime or factor them, but no extra information will be shown in the screen.

By pressing the Help button the calculator will show how to use it. Only the section titles are shown. You can expand the sections by clicking on the title. For example, you can see all operators and functions supported by the calculator by clicking in the Expressions section title.

In the next example, we will factor random 4-digit numbers. Each time you click on Factor button, you will see a different number being factored.

We can change the arguments of random function so we can factor random 40-digit numbers. Notice that the two asterisks mean power.

The calculator can also evaluate the random numbers without factoring them or it can test them for primality.

Now we will factor a 94-digit number: 10 to the 93 plus 27. The last factor is composite, so the calculator first attempt to factor this number using the Elliptic Curve Method (ECM) and then using the Self-Initializing Quadratic Sieve (SIQS).

The calculator shows the progress of SIQS, including the estimated time to finish the sieve stage. In the sieve stage the calculator computes partial and full relations. Sometimes two partial relations can be combined to get a full relation. The number of relations to collect is slightly higher than the number of primes given in the SIQS parameters.

When SIQS progresses, more partial relations can be combined, so it runs faster.

After the sieve stage finishes, the relations are processed using a method named Block Lanczos in order to get the factorization. This Block Lanczos is very fast compared with the sieve stage.

After SIQS finishes, you can see the 94-digit number completely factored.

After the factors and extra information, the calculator shows the statistics for this factorization session.

To end the first part of the tutorial, a 78-digit number will be factored: 10 to the 77 plus 3. We can see the progress of the Elliptic Curve Method by looking at the curve number.

We can close the Web page and open it again or refresh the page by pressing the button F5. We can see that the factorization progress is not lost.

The algorithm SIQS requires a lot of memory, so it cannot be stopped. If you refresh the page, SIQS will restart from the beginning.

I hope you found this first part of the tutorial useful.