Why is this happening to my software? An illegal instruction error.

[Timon Gehr]

On 6/19/24 01:07, Murilo wrote:
> I've created a software which performs the Fermat's Primality Test, 
> however if I input a very big number it causes an error saying "Illegal 
> instruction (core dumped)". Does anyone know why?
> 
> I've used GDB and here is the message:
> Program received signal SIGILL, Illegal instruction.
> 0x00005555555e40b0 in 
> _D3std8internal4math11biguintcore7BigUint3powFNaNbNfNkMSQCcQCbQBvQBtQBjmZQs ()
> 
> Here is the link to the source code: 
> https://github.com/MuriloMir/Fermat-primality-test

Looking at the code, this is probably the cause:

```
if (BigInt(tester) ^^ number % number != tester)
```

This uses roughly as much memory as `number` is big, times the `log` of 
`tester`. You'd have to implement your own modular exponentiation that 
does not compute the full intermediate result, the you use only roughly 
`log` of `number` memory.