Faits:
Faits:
A. X._, né en 1971, possède conjointement les nationalités suisse et française. Il a vécu en France où il a été exempté du service national actif par la Commission locale d'aptitude siégeant à Marseille le 20 mars 1990 avant de s'établir en Suisse le 1er juin de la même année. D'abord installé à A._ (VS), il a déménagé à B._ (VS) en 1996, commune au sein de laquelle il a changé de domicile à plusieurs reprises.
Un livret de service a été établi au nom de X._ par le chef de section militaire (ci-après: le chef de section) de B._ à l'occasion d'un changement d'adresse. Suite à cette mesure, le 7 octobre 2003, l'Office cantonal des affaires militaires (ci-après: l'Office cantonal) a réclamé le paiement de taxes d'exemption de l'obligation de servir (ci-après: la taxe d'exemption) pour les périodes d'assujettissement 1997 à 2002 (soit les périodes de taxation 1998 à 2003) à l'intéressé qui a contesté cette décision.
Le 19 décembre 2003, l'Etat-major général de l'armée suisse (ci-après: l'Etat-major) a décidé que X._ ne pourrait pas être incorporé dans l'armée suisse, qu'il était affecté aux doubles nationaux non incorporés et qu'il n'était pas astreint au service militaire.
L'Office cantonal a considéré que la décision de l'Etat-major ne déployait d'effets que pour l'avenir. En conséquence, il a refusé à X._ l'exonération des taxes d'exemption litigieuses, d'abord par décision du 3 mars 2004, puis par décision sur réclamation du 16 juin 2004.
Par arrêt du 22 décembre 2004, la Commission cantonale de recours en matière fiscale du canton du Valais (ci-après: la Commission cantonale de recours) a rejeté le recours formé par X._. Elle a considéré, en bref, que la décision de l'Etat-major affectant X._ aux doubles nationaux non incorporés n'avait pas d'effet rétroactif et qu'en conséquence, l'intéressé était astreint au paiement des taxes d'exemption litigieuses.
Par arrêt du 22 décembre 2004, la Commission cantonale de recours en matière fiscale du canton du Valais (ci-après: la Commission cantonale de recours) a rejeté le recours formé par X._. Elle a considéré, en bref, que la décision de l'Etat-major affectant X._ aux doubles nationaux non incorporés n'avait pas d'effet rétroactif et qu'en conséquence, l'intéressé était astreint au paiement des taxes d'exemption litigieuses.
B. Agissant par la voie du recours de droit administratif, X._ demande principalement au Tribunal fédéral d'annuler l'arrêt de la Commission cantonale de recours du 22 décembre 2004 et de lui allouer une indemnité d'un montant de 1'000 fr., à titre de réparation du tort moral. Il demande subsidiairement l'annulation partielle de l'arrêt de la Commission cantonale de recours du 22 décembre 2004 en raison de la prescription partielle de la dette ainsi qu'une indemnité d'un montant de 500 fr., à titre de réparation du tort moral. En outre, X._ sollicite l'assistance judiciaire.
La Commission cantonale de recours, l'Office cantonal ainsi que l'Administration fédérale des contributions concluent au rejet du recours.
La Commission cantonale de recours, l'Office cantonal ainsi que l'Administration fédérale des contributions concluent au rejet du recours.
C. Par ordonnance présidentielle du 21 avril 2005, l'effet suspensif a été conféré au recours.

Le Tribunal fédéral considère en droit:
Le Tribunal fédéral considère en droit:
1. Le Tribunal fédéral examine d'office et avec une pleine cognition la recevabilité des recours qui lui sont soumis (<ref-ruling> consid. 1 p. 174, 185 consid. 1 p. 188; <ref-ruling> consid. 1 p. 227, et les arrêts cités).
1.1 Rendue par une autorité de dernière instance cantonale en application de la loi fédérale du 12 juin 1959 sur la taxe d'exemption de l'obligation de servir (LTEO; RS 661, ci-après: la loi sur la taxe d'exemption), la décision attaquée est fondée sur le droit public de la Confédération (art. 5 PA). La voie du recours de droit administratif est ouverte selon l'art. 97 al. 1 OJ, mis en relation avec les art. 98 al. 1 let. g OJ et 31 al. 3 LTEO. Les clauses d'exclusion des art. 99 à 101 OJ ne s'appliquent pas. Le présent recours est ainsi recevable.
1.2 A teneur de l'art. 104 OJ, le recours de droit administratif peut être formé pour la violation du droit fédéral, y compris l'excès et l'abus du pouvoir d'appréciation (lettre a) et la constatation inexacte ou incomplète des faits pertinents (lettre b). Le Tribunal fédéral examine avec une cognition pleine le grief de violation du droit fédéral (<ref-ruling> consid. 3 p. 298, 385 consid. 3 p. 388), qui comprend la Constitution fédérale (<ref-ruling> consid. 3 p. 388). La décision attaquée émane d'une autorité judiciaire; partant, le Tribunal fédéral est lié par les faits constatés, sauf s'ils sont manifestement inexacts ou incomplets ou s'ils ont été établis au mépris des règles essentielles de la procédure (art. 105 al. 2 OJ).
1.3 Les conclusions du recourant en versement d'une indemnité pour tort moral n'étaient pas objet de la procédure cantonale et sont donc irrecevables.
1.3 Les conclusions du recourant en versement d'une indemnité pour tort moral n'étaient pas objet de la procédure cantonale et sont donc irrecevables.
2. 2.1 Tout homme de nationalité suisse est astreint au service militaire ou au service civil de remplacement (art. 59 al. 1 Cst.; art. 2 al. 1 de la loi fédérale du 3 février 1995 sur l'armée et l'administration militaire, LAAM; RS 510.10, ci-après: la loi sur l'armée). Les obligations militaires comprennent notamment le service militaire ou civil et le paiement, le cas échéant, de la taxe d'exemption (art. 2 al. 2 LAAM). Y sont assujettis, les citoyens suisses astreints au service, domiciliés en Suisse ou à l'étranger, qui au cours de l'année d'assujettissement n'ont pas été incorporés pendant plus de six mois dans une formation de l'armée et ne sont pas astreints au service civil (art. 2 al. 1 let. a LTEO).
L'obligation de servir (et donc de payer la taxe d'exemption) vaut également pour les doubles nationaux (arrêt 2A.339/1996 du 12 mai 1997, Archives 66 251 consid. 3 p. 253). Toutefois, les Suisses doubles nationaux ne sont pas astreints au service militaire en Suisse s'ils ont accompli leurs obligations militaires ou des services de remplacement dans l'autre Etat dont ils possèdent aussi la nationalité (art. 5 al. 1 première phrase LAAM). Demeurent réservées les obligations de s'annoncer et de s'acquitter de la taxe d'exemption, sous réserve de conventions internationales contraires ou prévoyant d'autres modalités (voir art. 5 al. 2 et 5 al. 3 LAAM; <ref-ruling> consid. 1 p. 58).
2.2 Les personnes qui possèdent concurremment les nationalités suisse et française entrent dans le champ d'application de la Convention du 16 novembre 1995 entre la Suisse et la France relative au service militaire des doubles nationaux (RS 0.141.134.92; ci-après: la Convention 1995; art. 1 de la Convention 1995). Ce traité a été conclu par le Conseil fédéral suisse et le Gouvernement de la République française désireux d'épargner des difficultés en matière d'obligations militaires aux personnes qui possèdent conjointement les nationalités suisse et française. Entré en vigueur le 1er mai 1997, il remplace la Convention entre la Suisse et la France relative au service militaire des doubles nationaux, conclue le 1er août 1958 (RO 1959 p. 223; ci-après: la Convention 1958).
La Convention 1995 dispose:
"Art. 2 Obligations militaires
L'expression "obligations militaires" s'entend:
a) pour la France: du service national dans toutes ses formes,
b) pour la Suisse: du service militaire, du service civil et du paiement de la taxe d'exemption de ces services.
Art. 3 Principes
1. Le double-national n'est tenu d'accomplir ses obligations militaires qu'à l'égard d'un seul des deux Etats.
2. Le double-national accomplit ses obligations militaires dans l'Etat où il a sa résidence permanente au 1er janvier de l'année au cours de laquelle il atteint l'âge de 18 ans.
Il peut néanmoins déclarer vouloir accomplir ses obligations militaires à l'égard de l'autre Etat avant d'avoir atteint l'âge de 19 ans.
Le double-national qui a déjà commencé, sur sa demande, à accomplir ses obligations militaires dans l'un des deux Etats avant l'âge de 18 ans, les terminera dans cet Etat.
3. Le double-national justifie sa résidence permanente par la production d'un certificat conforme au modèle A annexé à la présente convention. Ce document est délivré par les autorités désignées par les deux Etats et adressé par le double-national au représentant consulaire de l'Etat où il sera libéré des obligations militaires.
(...).
Art. 5 Certificat de situation
Le double-national visé aux art. 3 ou 4 justifie de sa situation à l'égard de l'Etat où il n'est pas appelé à servir, sur demande de ce dernier, par la production d'un certificat conforme au modèle C annexé à la présente convention.
Art. 6 Résidence permanente
1. La résidence permanente s'apprécie en tenant compte du lieu où le double-national possède le centre de ses intérêts principaux.
(...).
Art. 7 Obligations de réserve
Le double-national n'est soumis aux obligations de réserve ou au paiement de la taxe d'exemption du service militaire ou civil que dans l'Etat où il est tenu d'accomplir ses obligations militaires."
A la différence de la Convention 1995 (cf. art. 3 paragraphe 2 Convention 1995), la Convention 1958 prévoyait: "les doubles-nationaux qui résident dans l'un ou l'autre des deux Etats sont tenus d'accomplir leurs obligations militaires légales dans l'Etat où ils ont leur résidence permanente à l'âge de dix-neuf ans révolus" (art. 2 paragraphe 1 première phrase Convention 1958).
2.3 En l'occurrence, au moment de la décision de taxation, le recourant, né le 18 mars 1971, était âgé de plus de 25 ans et ne pouvait en conséquence plus participer au recrutement (art. 8 al. 2 LAAM); toutefois, n'ayant pas atteint la limite des 34 ans, il restait tenu d'accomplir ses obligations militaires (art. 5 de l'ordonnance fédérale du 30 août 1995 sur la taxe d'exemption de l'obligation de servir [OTEO; RS 661.1, ci-après: l'ordonnance sur la taxe d'exemption] et 13 al. 2 lettre a LAAM). Il devait donc payer la taxe d'exemption (art. 26 al. 1 LTEO), sauf convention internationale contraire, notamment. Or le recourant, qui possède conjointement les nationalités suisse et française, peut se prévaloir de la Convention 1995.
2.4 Selon la Convention 1995, le double national n'est tenu d'accomplir ses obligations militaires que dans un seul Etat, celui où il a sa résidence permanente (au sens de l'art. 6 Convention 1995) au 1er janvier de l'année au cours de laquelle il atteint l'âge de 18 ans (art. 3 paragraphes 1 et 2 Convention 1995). En l'occurrence, le recourant avait sa résidence permanente en France le 1er janvier de l'année de ses 18 ans, soit le 1er janvier 1989. C'est donc dans cet Etat qu'il devait accomplir ses obligations militaires ou payer la taxe d'exemption (art. 7 Convention 1995).
Le recourant est arrivé en Suisse le 1er juin 1990 et peu après a fait établir par la Préfecture des Alpes-maritimes un certificat de résidence (modèle A) daté du 17 juillet 1990 et qui figure au dossier. Le recourant soutient, mais sans l'établir, que ce certificat aurait été remis au chef de section de la commune de A._. Ces allégations ne sont pas vérifiables, car les faits sont anciens et le chef de section concerné est aujourd'hui à la retraite. Toutefois, la version du recourant est suffisamment vraisemblable pour qu'on puisse la retenir. On voit en effet mal pour quel motif le recourant aurait fait établir un certificat de résidence si ce n'est pour le remettre aux autorités compétentes.
Le recourant devait adresser ce certificat de résidence au représentant consulaire de l'Etat où il serait libéré de ses obligations militaires (art. 3 paragraphe 3 Convention 1995), soit le Consul de Suisse en France. Cette prescription se comprend à la lecture de l'art. 3 paragraphe 2 de la Convention 1995 ainsi que de l'art. 2 paragraphe 1 de la Convention 1958 qui est son pendant et prévoit que le certificat, délivré par les autorités compétentes, doit être adressé par le double national au représentant consulaire de l'Etat où il n'était pas appelé à servir et dans le ressort duquel se trouve sa résidence. Le double national résidant dans l'un des deux Etats n'accomplit pas ses obligations militaires dans l'Etat où il ne réside pas, lequel doit en être informé. Par simplification, le double national adresse le certificat de résidence au représentant consulaire de l'Etat où il est libéré des obligations militaires.
En l'espèce, le recourant a adressé le certificat de résidence au chef de section de la commune de A._n qui n'est pas l'autorité désignée par les Conventions 1958 et 1995. Cela s'explique: le recourant a fait établir ledit certificat le 17 juillet 1990 alors qu'il avait quitté la France pour la Suisse. Exiger du recourant qu'il passe la frontière pour remettre le certificat de résidence au Consul de Suisse en France pour que ce dernier puisse l'adresser aux autorités suisses relèverait du formalisme excessif; ce d'autant plus que le chef de section est l'autorité compétente au Valais pour l'annonce de l'arrivée ou du départ de l'assujetti à la taxe d'exemption (art. 3 lettre a de la loi valaisanne du 11 février 1998 d'application de la loi sur la taxe d'exemption [LALTEO; RSVS 660.1]). Le recourant a ainsi rempli ses obligations d'annonce (au sens des art. 5 al. 2 et 7 LAAM).
Enfin, il convient de relever que c'est le 16 octobre 2003 que l'Office cantonal a requis du recourant un certificat de situation (modèle C) prévu par l'art. 5 de la Convention 1995. Le ministère français de la défense a établi ce certificat le 24 novembre 2003. Le recourant l'a adressé aux autorités suisses le 9 décembre 2003. Le 19 décembre 2003 l'Etat-major, se fondant notamment sur ce document, a décidé que le recourant était au bénéfice de la Convention 1995, qu'il ne pouvait être incorporé dans l'armée suisse mais était affecté aux doubles nationaux non incorporés et qu'il n'était pas astreint au service militaire.
La production du certificat de situation n'est pas une obligation: l'Etat où le double national n'est pas appelé à servir peut le demander (art. 5 Convention 1995). Or, en l'espèce, le recourant, auquel on ne peut adresser aucun reproche de ce point de vue, a agi dès la réquisition de l'Office cantonal. Il a donc pleinement rempli les obligations de procédure qui lui incombaient vis-à-vis des autorités suisses.
La production du certificat de situation n'est pas une obligation: l'Etat où le double national n'est pas appelé à servir peut le demander (art. 5 Convention 1995). Or, en l'espèce, le recourant, auquel on ne peut adresser aucun reproche de ce point de vue, a agi dès la réquisition de l'Office cantonal. Il a donc pleinement rempli les obligations de procédure qui lui incombaient vis-à-vis des autorités suisses.
3. En définitive, seule demeure litigieuse la question de savoir si le recourant doit le paiement des taxes d'exemption pour les périodes d'assujettissement 1997 à 2002, soit les périodes de taxation 1998 à 2003. L'Office cantonal a renoncé à réclamer le paiement des taxes pour les périodes antérieures - lesquelles sont prescrites (art. 38 al. 1 première phrase LTEO) - et postérieures. Pour les périodes postérieures, l'Office cantonal a admis qu'en vertu de la décision de l'Etat-major du 19 décembre 2003, le recourant, au bénéfice de la Convention 1995, ne devait pas payer la taxe d'exemption.
3.1 La période de taxation est le temps au cours duquel se déroule la procédure tendant à la détermination du revenu imposable et du montant de l'impôt dû (Ryser/Rolli, Précis de droit fiscal suisse [impôts directs], Berne 2002 p. 412/413). Au cours de cette procédure, les autorités compétentes en droit militaire déterminent le montant de la taxe d'exemption due par l'assujetti. La taxe est fixée chaque année (art. 25 al. 1 LTEO). L'année de taxation est, en règle générale, l'année civile qui suit l'année d'assujettissement (art. 25 al. 2 LTEO). La décision de taxation ne déploie ainsi ses effets que pour la période de taxation en cause et doit être renouvelée pour chaque nouvelle période.
Il n'en va pas ainsi pour la décision d'exonération prise en application de l'art. 4 LTEO; une telle décision déploie ses effets sur plusieurs périodes de taxation sans qu'il soit nécessaire de la renouveler. L'ordonnance sur la taxe d'exemption prévoit que "l'assujetti peut en tout temps demander que sa prétention à l'exonération ou à la réduction de la taxe soit soumise à un examen dont les conclusions auraient effet sur les taxations non encore passées en force" (art. 33 al. 1 OTEO). En conséquence, la décision de l'Etat-major, prise en application de l'art. 4 al. 1 lettre c LTEO est applicable à toutes les décisions de taxation qui ne sont pas encore passées en force, en particulier contre lesquelles il a été déposé une réclamation ou un recours en temps utile (concernant l'entrée en force de la taxation: Masshardt/Gendre, Commentaire IDN, Lausanne 1980, n. 5 ad art. 95, p. 404; Rivier, Droit fiscal suisse, L'imposition du revenu et de la fortune, Lausanne 1998, p. 170); une décision de taxation entrée en force ne saurait en revanche être modifiée après coup, (sous réserve d'une révision). Il s'agit donc de déterminer si la décision de taxation est entrée en force ou non pour savoir si l'assujetti peut prétendre à l'exonération ou à la réduction de la taxe d'exemption.
3.2 En l'espèce, le recourant est au bénéfice de la Convention 1995 et, conformément à la décision de l'Etat-major du 19 décembre 2003, ne doit pas payer la taxe d'exemption. La décision de l'Etat-major s'applique à toutes les périodes pour lesquelles aucune décision de taxation n'est entrée en force. Elle s'applique donc aux périodes d'assujettissement 1997 à 2002, soit les périodes de taxation 1998 à 2003, pour lesquelles aucune décision de taxation n'est entrée en force puisqu'elles font l'objet du présent recours. Pour ces périodes, le recourant ne doit pas le paiement de la taxe d'exemption. Le recours doit être admis sur ce point.
Certes, dans son arrêt 2A.135/2003 du 3 décembre 2003, Archives 73 579, le Tribunal fédéral avait eu à connaître du cas d'un assujetti possédant conjointement les nationalités suisse et française qui avait été mis au bénéfice de la Convention 1995 par décision de l'Etat-major. Il a jugé que la décision de l'Etat-major, prise en application de l'art. 4 al. 1 lettre c LTEO avait une valeur constitutive et ne produisait d'effets que pour l'avenir. Elle ne s'appliquait pas aux taxations entrées en force (sous réserve d'une révision) et n'avait pas d'effet rétroactif pour les taxations non entrées en force. S'agissant des décisions de taxation non entrées en force, le présent arrêt doit donc être considéré comme une modification de jurisprudence, conforme à la lettre de l'art. 33 al. 1 OTEO.
Le recours étant admis, il n'est pas nécessaire d'examiner les autres moyens soulevés par le recourant.
Le recours étant admis, il n'est pas nécessaire d'examiner les autres moyens soulevés par le recourant.
4. Vu ce qui précède, le recours doit être admis dans la mesure où il est recevable et l'arrêt attaqué annulé. Le recourant ne doit pas la taxe d'exemption pour les périodes d'assujettissement 1997 à 2002, soit les périodes de taxation 1998 à 2003.
Le recourant obtenant gain de cause pour l'essentiel, sa demande d'assistance judiciaire devient sans objet.
Le recourant, qui a procédé sans l'aide d'un mandataire professionnel, n'a pas droit à des dépens.
Le canton du Valais dont les intérêts pécuniaires sont en cause, doit payer les frais judiciaires (a contrario, art. 156 al. 2 OJ).
Le présent arrêt est rendu sans frais (art. 156 al. 1 et 2 OJ).

Par ces motifs, le Tribunal fédéral prononce:
Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est admis dans la mesure où il est recevable et l'arrêt attaqué est annulé. Le recourant ne doit pas la taxe d'exemption pour les périodes d'assujettissement 1997 à 2002, soit les périodes de taxation 1998 à 2003.
1. Le recours est admis dans la mesure où il est recevable et l'arrêt attaqué est annulé. Le recourant ne doit pas la taxe d'exemption pour les périodes d'assujettissement 1997 à 2002, soit les périodes de taxation 1998 à 2003.
2. La demande d'assistance judiciaire du recourant est sans objet.
2. La demande d'assistance judiciaire du recourant est sans objet.
3. Un émolument judiciaire de 2'000 fr. est mis à la charge du canton du Valais.
3. Un émolument judiciaire de 2'000 fr. est mis à la charge du canton du Valais.
4. Le présent arrêt est communiqué en copie au recourant, au Département de la sécurité et des institutions du canton du Valais, à la Commission de recours en matière fiscale du canton du Valais, ainsi qu'à l'Administration fédérale des contributions, section taxe d'exemption de l'obligation de servir.
Lausanne, le 10 janvier 2006
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le président: Le greffier: