|
Karim Belabas on Tue, 13 Jun 2023 11:09:32 +0200
|
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
|
Re: Why is "x*Mod(1/y, p)" 28.7% faster than "Mod(x/y, p)" ?
|
- To: hermann@stamm-wilbrandt.de
- Subject: Re: Why is "x*Mod(1/y, p)" 28.7% faster than "Mod(x/y, p)" ?
- From: Karim Belabas <Karim.Belabas@math.u-bordeaux.fr>
- Date: Tue, 13 Jun 2023 11:04:51 +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=1686647081; c=relaxed/relaxed; bh=qO8ditcgSBY/+P4rOpSDFk4IzsNbRbkNTlhJxXAGmak=; 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=Vv/1KBbYtG5eNA0krNbu1Oswa+E1vwNtQxjtO2TYb6ppkEJlQ5DXI9CrjwX9xoeECbwuSeP5BGvBu3EmfxrhS+ELr0uoEcVlQjUHcQxjLHvSEOX2SRBx60LVZP5iHSy/PPoiiFYp3LigGBIwQTDKYCBcfoITy4yeUUlFj107XAdPAS+d89gkUpEr0XYnLuwlYQa3Xql2DhtxVaRwPxgvktBT1LnM9r6GIbGdpxXLyf2iTn2jqk7mMLVIRUlNEiH6Dn5LLjaxjRkGq94wPr4w+DxKt9nA6CMX2fZehaZgiexwSDIDzU3zxEtQWSAHCVVzBTWQjTvplAtmSzxfq148i8CTP7EA2Psdi0/QPEBw9c+FbFsqXrYgRgQZmULh7spy6A0CaRuNVeJ2be+/rebX7FeUf6K/KD8dMxWxr0b3MTbfn2p4eq/bInJH/5AhwpnczLfbihkxB4R7oASNJaWc6X8B2jUnqjg7naAYutsQU95MXYGi2LivVOlo6yrkVESYjbYtN7VrQwk6pV+1Ug6mpQ/V2YConVHXI93Nh5ledSg+lA6VpLCB3G88srG5yQZQftjNSmGk9eIkz2lhmUl2dYD/kPl+SoCm3k02ZUHv1NcC9EiFvFH0lb0OGlMoBVFZixZGugBPkmyCazRIIwq+DV1EVANkRKYy5rTyi6VbGHA=
- Arc-seal: i=1; a=rsa-sha256; d=math.u-bordeaux.fr; s=openarc; t=1686647081; cv=none; b=cE8d8utRm0UnFJDfUSsZssdV2GJ0/BDNKwGBUr6G5j9QRl8sPuo2tIxPmgMCZ4EE1rJW9BB2bYvS6rnPV1mqkUm9F4Q3IomZbqlaom/oH4PyZM7ciczAFV2eprkHG4vieuAjV4O6spd/EiNSC43Xyfa/ytUsjCw+sEBSz/0FYqmF9RpQcXEazOLQWQ+VRV+B8ERxjoqOsydV6QP5aMGOzRSlrdcYWI9XkChzhCb2J1QAHMAunpokDpzJfowOPRJN4uCma/HYvEmNZ6l2fnPiwI8Hd/BpruO7meA+Amf4lQe5Lmx6B6aXUeqBKH7Tcs6ytXl/s4Xu748022ECjXQkY+pk7WvnZCI4d6NF4Pjvj/Uty7OiNi9Jix+o+Tbv13lGtxDL++ut7rkKDds6IiagxBRW0Keqaa8V5p2ZhBPEfFayWZkSYzA4GoJxISjcb55z90cN6Ywcwcl3HW0oglr2wa/SdqOAEnapzav1WXvLsU9sIOTFT45NIV/A3dYkM93LeDRvog5141VMvcuTkpUfpwiWieRg2pa2iUY/YVEmhXuiBtTzn+73waQkRsBDU4hmFWX6UShra9aONjNaa8Zp1mZ2lv/Rx0y1xmdLCRlG1pXj05sduUiDy+uCH7iPTkgx6pvizXTtQ4BUr0vsq9pt/MXtYG9kCUb03WgeBrpOdiM=
- Authentication-results: smail; arc=none
- Cc: pari-users@pari.math.u-bordeaux.fr
- Delivery-date: Tue, 13 Jun 2023 11:09:32 +0200
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=math.u-bordeaux.fr; s=2022; t=1686647081; bh=qO8ditcgSBY/+P4rOpSDFk4IzsNbRbkNTlhJxXAGmak=; h=Date:From:To:Cc:Subject:References:In-Reply-To:From; b=sPKgsK06U6peFU0h4Q8wXdOQYMXhq+wJBTkcDaolhnEYpy1M6mTcBdeguwZdzwA/1 JLQOp8Up6vh+ptrD5raibdqE3q0tZ/7CEKiEhXZvNoUE79VvVYNtFCtMQ9f/LpJIob 9IM46xxUcvN/tc5yWmuR6ndZsu6skFAK2gTkwdFIfLTEEZr/Od47OqQmx3seJRnrZ4 Ad3WtOsBXdr9azmOX19j9XovtsVBSK2C2x99XgaEyKHFTGW8xztRPodY0CfVLfEM3a Ug3lxnzBmMGxbU0ToyDXTJVgSxCmgs2XF1EIX43V5QQcNPd9B0Udj0z79MoWN+EUDT uhTI+kH7Bjmz3ITcbXKN9hUxHn5Og4vjtHf/VNfcQ5NGJKW2b6kSCcZt0rQ+Kq/6vm bz+9eUBh9dCA4TIAkG4zMs8XlvzElQgCGojtec50Qgbjywks5A+yiF+VjMyd1zjfUN vpQG+5F5H07x9aPyOYWAJ3+ZSbnr/Q6Zd+bmZgJvAQW6qmT0F7HnG72dMM9MVCO5gR lczgoQffivx8NmenSjS8ms8QaO675frZZDYJ/PrJHKqKXg13YoVGaNsj0S3ZOBATAA RVspR24Bz8SxMuv1x5SO09v5daRvX5eCMU+oTUhADIU1H0XDmFvbq0n4xPww7Bv99Y +uXcvFA2ONQmhIKQyH660a1g=
- In-reply-to: <377af14731173cebe20b6a41ed4859a1@stamm-wilbrandt.de>
- Mail-followup-to: hermann@stamm-wilbrandt.de, pari-users@pari.math.u-bordeaux.fr
- References: <377af14731173cebe20b6a41ed4859a1@stamm-wilbrandt.de>
* hermann@stamm-wilbrandt.de [2023-06-13 10:53]:
> "##" measures time in milliseconds.
>
> So I use a very big prime (1million decimal digits) and its sqrtm1 =
> sqrt(-1) (mod p) to see 3-digit millisecond runtimes, from this Pari/GP
> script:
> https://github.com/Hermann-SW/RSA_numbers_factored/blob/main/pari/sqrtm1.smallest_known_1million_digit_prime.gp
>
> 323ms is 28.7% faster than 453ms, what is the reason that "x*Mod(1/y, p)"
> outperforms "Mod(x/y, p)"?
x/y starts by computing the GCD of two large numbers, to reduce the
fraction to irreducible represention. This step is trivial in 1/y which
is obviously reduced.
This GCD step is unnecessary but must be performed since x/y requests it
(PARI doesn't support reducible fractions: they are reduced on the spot).
It is of the same order of difficulty as inverting the denominator mod p
[extended GCD].
Cheers,
K.B.
--
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/