• Top
  • Documentation
  • Books
  • Boolean-reasoning
  • Projects
  • Debugging
  • Std
  • Community
  • Proof-automation
  • Macro-libraries
  • ACL2
  • Interfacing-tools
  • Hardware-verification
  • Software-verification
    • Kestrel-books
      • Crypto-hdwallet
      • Apt
      • Error-checking
      • Fty-extensions
      • Isar
      • Kestrel-utilities
      • Set
      • Soft
      • C
      • Bv
      • Imp-language
      • Event-macros
      • Java
      • Bitcoin
      • Ethereum
      • Yul
      • Zcash
      • ACL2-programming-language
      • Prime-fields
      • Json
      • Syntheto
      • File-io-light
      • Cryptography
        • R1cs
        • Interfaces
        • Sha-2
        • Keccak
        • Kdf
        • Mimc
        • Padding
        • Hmac
        • Elliptic-curves
          • Secp256k1-attachment
          • Twisted-edwards
            • Twisted-edwards-mul
            • Twisted-edwards-mul-fast
            • Twisted-edwards-add
            • Twisted-edwards-point-orderp
            • Twisted-edwards-add-associativity
            • Twisted-edwards-mul-distributivity-over-scalar-addition
            • Twisted-edwards-neg-inverse
            • Twisted-edwards-mul-fast-nonneg
            • Twisted-edwards-curve
            • Twisted-edwards-mul-nonneg
            • Birational-montgomery-twisted-edwards
            • Twisted-edwards-compress
            • Twisted-edwards-neg
            • Twisted-edwards-sub
            • Point-on-twisted-edwards-p
            • Twisted-edwards-curve-completep
            • Twisted-edwards-point-order-leastp
            • Twisted-edwards-only-points-with-x-0-or-y-1
            • Twisted-edwards-add-inverse-uniqueness
            • Twisted-edwards-distributivity-of-neg-over-add
            • Twisted-edwards-mul-associativity
            • Twisted-edwards-zero
            • Twisted-edwards-add-closure
            • Twisted-edwards-point-orderp-of-neg
            • Twisted-edwards-mul-of-mod-order
            • Twisted-edwards-zero-identity
            • Twisted-edwards-add-cancel-left
            • Twisted-edwards-mul-of-neg
            • Twisted-edwards-add-commutative
          • Montgomery
          • Short-weierstrass-curves
          • Birational-montgomery-twisted-edwards
          • Has-square-root?-satisfies-pfield-squarep
          • Secp256k1
          • Secp256k1-domain-parameters
          • Secp256k1-types
          • Pfield-squarep
          • Secp256k1-interface
          • Prime-field-extra-rules
          • Points
        • Attachments
        • Elliptic-curve-digital-signature-algorithm
      • Number-theory
      • Lists-light
      • Axe
      • Builtins
      • Solidity
      • Helpers
      • Htclient
      • Typed-lists-light
      • Arithmetic-light
    • X86isa
    • Axe
    • Execloader
  • Math
  • Testing-utilities

• Twisted-edwards

Twisted-edwards-curve-completep

Check if a twisted Edwards curve is complete.

Signature

(twisted-edwards-curve-completep curve) → yes/no

Arguments

curve — Guard (twisted-edwards-curvep curve).

Returns

yes/no — Type (booleanp yes/no).

According to the paper on twisted Edwards curves referenced in twisted-edwards, this is the case when a is a square and d is a non-square. Completeness means that the addition formula (see twisted-edwards-add) works for every pair of point on the curve. In particular, the denominators of the coordinates of the sum are both always different from 0 when the curve is complete.

Definitions and Theorems

Function: twisted-edwards-curve-completep

(defun twisted-edwards-curve-completep (curve)
  (declare (xargs :guard (twisted-edwards-curvep curve)))
  (let ((acl2::__function__ 'twisted-edwards-curve-completep))
    (declare (ignorable acl2::__function__))
    (and (pfield-squarep (twisted-edwards-curve->a curve)
                         (twisted-edwards-curve->p curve))
         (not (pfield-squarep (twisted-edwards-curve->d curve)
                              (twisted-edwards-curve->p curve))))))

Theorem: booleanp-of-twisted-edwards-curve-completep

(defthm booleanp-of-twisted-edwards-curve-completep
  (b* ((yes/no (twisted-edwards-curve-completep curve)))
    (booleanp yes/no))
  :rule-classes :rewrite)

Theorem: twisted-edwards-curve-completep-of-twisted-edwards-curve-fix-curve

(defthm
 twisted-edwards-curve-completep-of-twisted-edwards-curve-fix-curve
 (equal (twisted-edwards-curve-completep
             (twisted-edwards-curve-fix curve))
        (twisted-edwards-curve-completep curve)))

Theorem: twisted-edwards-curve-completep-twisted-edwards-curve-equiv-congruence-on-curve

(defthm
 twisted-edwards-curve-completep-twisted-edwards-curve-equiv-congruence-on-curve
 (implies (twisted-edwards-curve-equiv curve curve-equiv)
          (equal (twisted-edwards-curve-completep curve)
                 (twisted-edwards-curve-completep curve-equiv)))
 :rule-classes :congruence)