Endomorphisms and Factoring
 

1. I need to find out a program that only deals in machine level 0s and 1s. What I mean is unlike C++, Java, etc...decimals are not converted to binary but it is a program where every number dealing is binary. There should be no fixed integer range so large blocks can be dealt with in a good way.

2. So, the supposed mersenne prime to binary. The about to be tested primes(P) are also in binary.

Then, one uses endomorphisms [f][/P] which makes all the P appearances in the block supposed Mersenne prime to 000 s of P length. Then another endomorphism just performs subtraction right from the first or second place below 1's in the block. This can be created as a function.

I am just looking for a program that handles large binary numbers. I am also open to knowing more about endomorphisms and factoring if there exists such theory.

Just putting this out there for consideration...

Do any other regular Mersenne Forum members find it a bit odd that there are many new participants who get the "lingo", but ask really stupid questions?

[QUOTE=chalsall;462317]Just putting this out there for consideration...

Do any other regular Mersenne Forum members find it a bit odd that there are many new participants who get the "lingo", but ask really stupid questions?[/QUOTE]

Could be my fault, I think I once posted a link to the forum, on a youtube comment, on a numberphile video.

[QUOTE=manasi;462316]1. I need to find out a program that only deals in machine level 0s and 1s. What I mean is unlike C++, Java, etc...decimals are not converted to binary but it is a program where every number dealing is binary.
[/QUOTE]

[URL="http://pari.math.u-bordeaux.fr/"]Pari/GP[/URL] has a function called binary(). For example:

[CODE]? n=2^17-1;
? binary(n)
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[/CODE]

That is a rude message. Is it not? If my question is that trivial to you, then you could have done the honours of answering it. Did you get my post?

Thank You. I will check out PARI/GP.

[QUOTE=manasi;462321]Thank You. I will check out PARI/GP.[/QUOTE]

[url]https://en.wikipedia.org/wiki/Machine_code[/url] might also be something to read.

@science man: That is not what I am saying, people use high level language. It converts everything to machine code. My problem is with HLLs and their fixd integer range which makes prime factoring or mathematical computations difficult. So I am looking for a modern low level program where the number system is binary and like machine language , since large amounts of bits and bytes are stored, working with them is simple. Prime factoring would be very comfortable with elementary computations.

[QUOTE=manasi;462320]That is a rude message. Is it not? If my question is that trivial to you, then you could have done the honours of answering it. Did you get my post?[/QUOTE]

A very wise man once told me that I didn't need to bat at every ball.

He also wisely told me that sometimes you simply touch the ball to cause a little trouble, when it was worth the effort.

RIP ROK.

[QUOTE=manasi;462325]@science man: That is not what I am saying, people use high level language. It converts everything to machine code. My problem is with HLLs and their fixd integer range which makes prime factoring or mathematical computations difficult. So I am looking for a modern low level program where the number system is binary and like machine language , since large amounts of bits and bytes are stored, working with them is simple. Prime factoring would be very comfortable with elementary computations.[/QUOTE]

If you have linux you could use the [URL="https://en.wikipedia.org/wiki/Bc_%28programming_language%29"]bc language[/URL]:

[CODE]bc 1.06.95
Copyright 1991-1994, 1997, 1998, 2000, 2004, 2006 Free Software Foundation, Inc.
This is free software with ABSOLUTELY NO WARRANTY.
For details type `warranty'.
ibase=2
obase=2
101010*101001
11010111010
[/CODE]

I think you can get it for Windows and iPhone :smile:

[QUOTE=manasi;462325]@science man: That is not what I am saying, people use high level language. It converts everything to machine code. My problem is with HLLs and their fixd integer range which makes prime factoring or mathematical computations difficult. So I am looking for a modern low level program where the number system is binary and like machine language , since large amounts of bits and bytes are stored, working with them is simple. Prime factoring would be very comfortable with elementary computations.[/QUOTE]

Do you mean something like GMP?

Yes, every language still fundamentally works in binary, but typically in fixed-width binary. GMP is a library for C (and therefore all its derivatives) that allows for arbitrary-size integers. It's very common in big number prime testing and factorization code.

[url]https://en.wikipedia.org/wiki/List_of_arbitrary-precision_arithmetic_software[/url]

A lot of the languages and software packages in the above list use GMP under the hood.

[QUOTE=manasi;462316]1. I need to find out a program that only deals in machine level 0s and 1s. What I mean is unlike C++, Java, etc...decimals are not converted to binary but it is a program where every number dealing is binary.[/QUOTE]

In almost every modern language, certainly including PARI/GP, C++, and Java, [i]all[/i] numbers are in binary unless you go through a lot of extra effort to avoid that (via BCD or other formats). You enter numbers in decimal, but they are stored and processed exclusively in binary and only re-converted into decimal when you output them.

[QUOTE=manasi;462316]There should be no fixed integer range so large blocks can be dealt with in a good way.[/QUOTE]

This only slightly less common. Some languages like PARI/GP and Python have bignums built-in so you can't reasonably overflow, and many others like C and Java have libraries that can support them as needed.

[QUOTE=paulunderwood;462328]If you have linux you could use the [URL="https://en.wikipedia.org/wiki/Bc_%28programming_language%29"]bc language[/URL]:

[CODE]bc 1.06.95
Copyright 1991-1994, 1997, 1998, 2000, 2004, 2006 Free Software Foundation, Inc.
This is free software with ABSOLUTELY NO WARRANTY.
For details type `warranty'.
ibase=2
obase=2
101010*101001
11010111010
[/CODE]

I think you can get it for Windows and iPhone :smile:[/QUOTE]

Thanks

[QUOTE=Dubslow;462329]Do you mean something like GMP?

Yes, every language still fundamentally works in binary, but typically in fixed-width binary. GMP is a library for C (and therefore all its derivatives) that allows for arbitrary-size integers. It's very common in big number prime testing and factorization code.

[url]https://en.wikipedia.org/wiki/List_of_arbitrary-precision_arithmetic_software[/url]

A lot of the languages and software packages in the above list use GMP under the hood.[/QUOTE]

Thanks. I learnt about GMP. I was talking about ASCII specifications and space a signed or unsigned int occupies. I will explain in next post.

I am probably wrong on this, but... Isn't the use of fixed length variables a matter of the machine word length, i.e. hardware stuff, not software stuff?

In other words, the use of decimal, binary, hexadecimal or whatever else is bound to the physical representation of the bits inside the computer registers. This means that a "binary, unbound bit-length language" is something as theoretical as a Turing Machine...

[QUOTE=CRGreathouse;462332]In almost every modern language, certainly including PARI/GP, C++, and Java, [i]all[/i] numbers are in binary unless you go through a lot of extra effort to avoid that (via BCD or other formats). You enter numbers in decimal, but they are stored and processed exclusively in binary and only re-converted into decimal when you output them.[/QUOTE]

Well, the only problem is there is a certain integer range that is acceptable as space for an integer(signed or unsigned int). There is a problem if you have to check a number like 2^10000019 -1 is prime or not. Most programs can not handle operations with large numbers.

Now, suppose I do not want to use Lucas Lehmer test but instead want to create endomorphisms that directly alter blocks of the binary sequence 2^10000019 -1 yielding a result with less operations. For instance, you could rule out division from {multiplication,division,subtraction} but only use {subtraction,multiplication}. There would be very large binary sequences. This is what I want to do to get results a different way.


[QUOTE=CRGreathouse;462332]This only slightly less common. Some languages like PARI/GP and Python have bignums built-in so you can't reasonably overflow, and many others like C and Java have libraries that can support them as needed.[/QUOTE]

Oh!

[QUOTE=manasi;462361]
Now, suppose I do not want to use Lucas Lehmer test but instead want to create endomorphisms that directly alter blocks of the binary sequence 2^10000019 -1 yielding a result with less operations. For instance, you could rule out division from {multiplication,division,subtraction} but only use {subtraction,multiplication}. There would be very large binary sequences. This is what I want to do to get results a different way.




Oh![/QUOTE]

Montgomery multiplication and binary exponentiation?

[QUOTE=manasi;462361]Now, suppose I do not want to use Lucas Lehmer test but instead want to create endomorphisms that directly alter blocks of the binary sequence 2^10000019 -1 yielding a result with less operations.[/QUOTE]

I don't know why you think it is possible to go faster than LL by working "directly"with binary. All existing programs work directly with binary.

[QUOTE=manasi;462361]Most programs can not handle operations with large numbers.
[/QUOTE]
Depends on what you call 'most'. Excel? calc.exe?

[QUOTE=manasi;462361]... This is what I want to do to get results a different way.

... Oh![/QUOTE]
In order to get results a different way you first need to read and learn what is already done.

Two Russian anecdotes come to mind:
1. "Can you play violin?" -- "I never tried but I think I can!". [SPOILER]This was popular [I]long[/I] before the Kruger & Dunning 1999 paper.[/SPOILER]
2. "Can you play (using a)* violin?" -- "I can! ...But it is very inconvenient - the cards** slip and fall over. Cello is much better."
______________
*In Russian, "to play violin" is a phrase with a preposition.
**And of course "play" in most minds means "play cards"

[QUOTE=ET_;462362]Montgomery multiplication and binary exponentiation?[/QUOTE]

I thought to use endomorphisms and work similar to modular arithmetic -

Start to compare size of two binary numbers minus zeroes at the end. Then just play with the blocks using endomorphisms. Different algorithm other than the two you mentioned. But then, as you say, perhaps machine specifies integer width.(hardware) So, I can not proceed on this line.

[QUOTE=CRGreathouse;462376]I don't know why you think it is possible to go faster than LL [/QUOTE]

No idea if I can go faster. Didn't exactly write and compare the two algorithms. Just wanted to try different.

[QUOTE=Batalov;462383]


In order to get results a different way you first need to read and learn what is already done.

[/QUOTE]

Thanks.
Very true.(i) I would like to know more about endomorphisms acting on binary sequences. (ii) Are they more/less helpful in factoring? I googled but did not get suitable results.

[QUOTE=manasi;462361]Well, the only problem is there is a certain integer range that is acceptable as space for an integer(signed or unsigned int). There is a problem if you have to check a number like 2^10000019 -1 is prime or not. Most programs can not handle operations with large numbers.
[/QUOTE]

That's precisely why I suggested GMP. Instead of writing [c]a = a + b*c[c], which is limited by the machine word size as you say, but with GMP you write, in C or any other language GMP supports, you write [c]mpz_addmul(a, b, c)[/c] which works for numbers a, b, c of arbitrary size, hundreds of digits, thousands of digits, etc.

Frankly, the things you say seem to indicate you know very little about how computers actually work, and your talk about "endomorphisms" is equally meaningless from a mathematical perspective. You have no idea what you're doing, which is why you got such a snarky response to your initial post.

[QUOTE=Dubslow;462404]That's precisely why I suggested GMP. Instead of writing [c]a = a + b*c[c], which is limited by the machine word size as you say, but with GMP you write, in C or any other language GMP supports, you write [c]mpz_addmul(a, b, c)[/c] which works for numbers a, b, c of arbitrary size, hundreds of digits, thousands of digits, etc.

Frankly, the things you say seem to indicate you know very little about how computers actually work, and your talk about "endomorphisms" is equally meaningless from a mathematical perspective. You have no idea what you're doing, which is why you got such a snarky response to your initial post.[/QUOTE]

Well, I know less about - GMP if you mean to say GMP has no restriction on space. I have been talking about working with very large numbers. I do know that decimal numbers are stored in binary or any data for that matter.

But what is the problem with f: [Z][/2] -> [Z][/2].
Well, I have been using homomorphisms(under * or +) on binary numbers. What is the problem with math? It is clear and very simple, is it not? Besides, this is an Algebra thread.

[QUOTE=manasi;462399]No idea if I can go faster. Didn't exactly write and compare the two algorithms. Just wanted to try different.[/QUOTE]

I don't mean that you shouldn't try, but that I don't see anything different. As far as I can tell your suggestion is to use binary, but everyone is using binary. :ermm:

[QUOTE=manasi;462406]Well, I know less about - GMP if you mean to say GMP has no restriction on space. I have been talking about working with very large numbers.[/QUOTE]

There are a number of different limitations to consider.

First are architectural limitations. I'm not sure what it is for GMP but for example in PARI/GP you can have t_REAL numbers up to almost 2^2^29 on 32-bit systems and 2^2^61 on 64-bit systems.

Next there are memory limitations. If you want to store 2^10^15 directly you need 10^15 bits of memory. On 64-bit systems this is more likely to cause trouble than architectural limitations.

Finally there are practical limitations imposed by the algorithms used. If you want to factor the numbers, it doesn't matter if you could store billions of digits because you won't live long enough for a current computer running current software to factor such a beast.

If the OP refers to Frobenius endomorphism of GF(N^2), this method is not deterministic. This was established by Grantham.
They are nothing more than PRP tests. And, owing to the work of Pomerance and Kim, they are not even as useful as a MR test. For the latter we have good estimates of the probability that the result of a test is in error. However, the Pomerance/Kim analysis will not work for your tests.

@OP:

1. Click on "Start" button
2. Click on "All programs"
3. Click on "Accessories"
4. Click on "Calculator"
5. Click on "View" and select "Programmer"
6. Click on "Bin" radio button.
7. Voila! Enjoy!

For how you talk, you seem not to be needing more... The only problem is that you may need to launch the magnifier program too (also in accessories) because as the binary number grows bigger, the digits become smaller, due to the limited space and non-sizeable window.. A real magnifier glass may do wonders... It can also be from plastic, it doesn't matter.

:razz:

Edit: tip: you can modify the numbers directly clicking on the powers of two on the gray area, you do not need to input all numbers bit by bit...

:razz: