number-theory-toolkit

# Number Theory Toolkit Skill ## Purpose Provide implementations and guidance for number theory algorithms commonly used in competitive programming. ## Capabilities - Modular arithmetic operations - Extended Euclidean algorithm - Chinese Remainder Theorem - Modular inverse and exponentiation - FFT/NTT for polynomial multiplication - Linear sieve implementations ## Target Processes - number-theory-algorithms - prime-algorithms - combinatorics-counting ## Algorithm Catalog ### Modular Arithmetic - Modular exponentiation (binary exp) - Modular inverse (Fermat/Extended GCD) - Modular square root (Tonelli-Shanks) ### GCD and Extensions - Euclidean algorithm - Extended Euclidean algorithm - Linear Diophantine equations ### Chinese Remainder Theorem - CRT for coprime moduli - General CRT ### FFT/NTT - Fast Fourier Transform - Number Theoretic Transform - Polynomial multiplication ## Input Schema ```json { "type": "object", "properties": { "algorithm": { "type": "string" }, "parameters": { "type": "object" }, "language": { "type": "string", "enum": ["cpp", "python", "java"] }, "modulo": { "type": "integer" } }, "required": ["algorithm"] } ``` ## Output Schema ```json { "type": "object", "properties": { "success": { "type": "boolean" }, "code": { "type": "string" }, "explanation": { "type": "string" }, "complexity": { "type": "string" } }, "required": ["success"] } ```