|
Karim Belabas on Sun, 12 May 2024 18:11:30 +0200
|
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
|
Re: p=randomprime(2^2000) is significantly slower than isprime(p)
|
- To: Georgi Guninski <gguninski@gmail.com>
- Subject: Re: p=randomprime(2^2000) is significantly slower than isprime(p)
- From: Karim Belabas <Karim.Belabas@math.u-bordeaux.fr>
- Date: Sun, 12 May 2024 18:11:04 +0200
- Arc-authentication-results: i=1; smail; arc=none
- Arc-message-signature: i=1; a=rsa-sha256; d=math.u-bordeaux.fr; s=openarc; t=1715530266; c=relaxed/relaxed; bh=3B+gcpMYprygiwpT6xCRvuws7UfkJoAFutlEW80o0VM=; h=DKIM-Signature:Date:From:To:Cc:Subject:Message-ID: Mail-Followup-To:References:MIME-Version:Content-Type: Content-Disposition:Content-Transfer-Encoding:In-Reply-To; b=MefTeP9QzPMiYqxcp0iEtvqVlNQ9xGyZnXTm0OWLIlY4c+Ih6nXoclSl2VThfCpnzc4WlPCOKegMz1g75ORiTE4yUfr/fcMo6SnlVFcdKf9n8XMcjsj9Hlwh6UXswMjGiDb8httuzgcF7BlM1AnpQ9xZUm4wiHPvCm9ZXVzFlakkyzSDrxRntlkTezHmj6fIScQrJwOz/HxGbM21uLtcQgVNZfui4Ew2uHpMRVrj1zFVUf6Lt972Em/6NEfesAQCAshr5hcWcnOH56mJ2DlXi8r2nyhOhaliyFgjV6orAxSyKnDgTAxI4/3la+8FyUddJKG7Rsjo3HyFxoOQh2BPanD51B0AfxZ8HQKz2/+SF0rkkSJ9xvZtyXtcuoWahZ1pyLGtp8O5AsfXe30Ia732NBpGr31brQo1omcrGjBHFJg6Fqb6foG3FN0h6J+DUTNoFKFzkk+a217LoiVLPqQW857lU3aJwuMABaCmX5wE2+hex/U+TcPx2832V/Spse/oqxfN5QeHbVAPEi2xhRK8X1PqE7vis5cZW/MlRTEB94Qt4+Dm2YKFhm3ZcG+Mg5lxnMO4va/Sx2BnuFVl+zycgXkxwVVjVLbdfDPjA6lB4pj+wwyTJGjDZPbN/dlwxzRH3zhjQ37QS9/ldKwpChfkekpGHC/f0kITWRmbc0fRazk=
- Arc-seal: i=1; a=rsa-sha256; d=math.u-bordeaux.fr; s=openarc; t=1715530266; cv=none; b=EfTCth5oZYXTUTvpziIYmQPyw3c8lEDWMN8VSVKXm7Wy7wH2uJXUYJ39/c7rr98jiVO4l6SFEMXuKMo5TIhEoCtXw1yXB1pnwfofNihTJRnBB1JTRBnuv6cbCKa170PPzD+cPgMmsnfxIYJhJmVXl7/R9QgL7OGTp0G97Ae4MSMW3m0GSz2Pih5nxvMj9RZQ3/ij9fNBqZJ9cEMu9vPnZkP18tOHyzNKjFETMPp9+nghXZqCpZb3ZWN0y+7RoWEQF4cjD5gFqkZXKmMO35J8EOJX/av7/DrXKCl8B0GHTXq0gkEA1LdkYcTKL/ogTDhu2h3FX13TI+yIyD6YE37DPFlKFgXIpyIV7KGYDcnDGY7H8jaEHH+j5lngp64koABqthR1eNmi+QKX/77QhYn6ChYwa1xioJysfKBoSkUY09RJ/scrAVwlOxzLGVHm5qjOkfW6XtdaHYULMXlmcEpyAOAV08WvGpzuA69a+OJLiXKzPMuQcuWx8o/YX5KNP+/Z+VNWlN0g1l440AHR/7TMfosNqDjh+aaMc60BlY4VQORFCGpk7zMo9+gE6uzpHpzevRLvfbdO40+GUKEKJxeZQvMvhWEwiM3H+jM1fIB3+uMF2DZXAJsqcJhUCGAk/gUqarbUw4xcCP1vCIc4kt1AaGzdeNI4fr4Gbee7yaxp+QY=
- Authentication-results: smail; dmarc=none header.from=math.u-bordeaux.fr
- Authentication-results: smail; arc=none
- Cc: pari-dev@pari.math.u-bordeaux.fr
- Delivery-date: Sun, 12 May 2024 18:11:30 +0200
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=math.u-bordeaux.fr; s=2022; t=1715530266; bh=3B+gcpMYprygiwpT6xCRvuws7UfkJoAFutlEW80o0VM=; h=Date:From:To:Cc:Subject:References:In-Reply-To:From; b=ifOS7nHa8TDsCbvky//gbMp1j2fVZmhLmxflgC732YUQoo5hvtZY7IEoS3TkrLHdy GS7o4v2KvKp+lNhumvyYyD1Q7RLBYauVNu167vPw1mQJkbdDQxcdkI0IGdyyLLptgQ +yRwxAwvUix/1kSDhclVdy3dBcHVv0abCKXYZQgXWvKNTORR/CXBix7I2O9OraQOmV PJ0RLrQvagDsVrR3jiNN2PpozjBF3DxipCYV3UHpAmc8W8RhRL/fBjXuQ0UQCvCdt9 sl/vtEh3stbSm0A8F0YsGp6lRUIoSQIc+HE17bV/t2La36fziMx4u7OEs0HY2lb8p5 RoKrz0j+QKmpYHZjMIyA1boJDu6UmADB7T+5JkLFQ7nPJyp8HHaaCoMFrtcho1ZXX1 V/3gMLsXhEt6j937TRZDn1bPTz8o2P35Njt9cyyPcR7mJ4/foax5HiR+dgReYJ3b9i 7MrzxTmSz0c8R0b2amd1O7yDhf4KAMT5TDl2y4ovBkK54gLWP2DaSxvVyMHke6ism6 My9ELf/v4vbaAZzULCIa/Kynw9CIIBUWFYahtwMO1xWazcVZbixa8Tn3BesRaY4UUY 0MGqyQ3LgopuL4OFrlEBsICy9GDyugHD1xdCEY4F+OHsOzWzNepXLPJXrctHK5oAAL ufW3D86MLZNMwC/4Vtp6AIb4=
- In-reply-to: <CAGUWgD868__S5WXXZMXUNi85V_BAxBp1eWGmJsXhM9zTm68oNQ@mail.gmail.com>
- Mail-followup-to: Georgi Guninski <gguninski@gmail.com>, pari-dev@pari.math.u-bordeaux.fr
- References: <CAGUWgD8XoGdsdR0ammRUG6EhVoeJVPM8Yvp6KSUie1F4U_cCvQ@mail.gmail.com> <CAGUWgD868__S5WXXZMXUNi85V_BAxBp1eWGmJsXhM9zTm68oNQ@mail.gmail.com>
* Georgi Guninski [2024-05-12 11:45]:
[...]
> isprime(p) is slower than randomprime(p):
Which makes sense since randomprime() only performs a strong pseudoprimality
proof and not a full primality proof. See ?? randomprime
Cheers,
K.B.
> ? default(timer,1)
> ? setrand(1)
> ? p=randomprime(2^2000)
> time = 747 ms.
> ? isprime(p)
> time = 14,758 ms.
> %4 = 1
> ? ispseudoprime(p)
> time = 40 ms.
> %5 = 1
--
Pr. Karim Belabas, U. Bordeaux, Vice-président en charge du Numérique
Institut de Mathématiques de Bordeaux UMR 5251 - (+33) 05 40 00 29 77
http://www.math.u-bordeaux.fr/~kbelabas/